Поиск максимального пространственного алгоритма в O (nlogn) [duplicate]

В дополнение к подходу грубой силы существует три способа решения этой проблемы. Я запишу их все. Коды java прошли тесты на онлайн-сайте судьи под названием leetcode: http://www.leetcode.com/onlinejudge#question_84 . поэтому я уверен, что коды верны.

Решение 1: динамическое программирование + n * n матрица как кеш

время: O (n ^ 2), пробел: O (n ^ 2 )

Основная идея: используйте n * n-матрицу dp [i] [j] для кеширования минимальной высоты между баром [i] и баром [j]. Начните заполнять матрицу из прямоугольников шириной 1.

public int solution1(int[] height) {

    int n = height.length;
    if(n == 0) return 0;
    int[][] dp = new int[n][n];        
    int max = Integer.MIN_VALUE;

    for(int width = 1; width <= n; width++){

        for(int l = 0; l+width-1 < n; l++){

            int r = l + width - 1;

            if(width == 1){
                dp[l][l] = height[l];
                max = Math.max(max, dp[l][l]);
            } else {                    
                dp[l][r] = Math.min(dp[l][r-1], height[r]);
                max = Math.max(max, dp[l][r] * width);
            }                
        }
    }

    return max;
}

Решение 2: динамическое программирование + 2 массива в качестве кеша.

время: O (n ^ 2), пробел: O (n)

Основная идея: это решение похоже на решение 1, но экономит некоторое пространство. Идея состоит в том, что в решении 1 мы строим матрицу из строки 1 в строку n. Но в каждой итерации только предыдущая строка способствует построению текущей строки. Таким образом, мы используем два массива в качестве предыдущей строки и текущей строки по очереди.

public int Solution2(int[] height) {

    int n = height.length;
    if(n == 0) return 0;

    int max = Integer.MIN_VALUE;

    // dp[0] and dp[1] take turns to be the "previous" line.
    int[][] dp = new int[2][n];      

    for(int width = 1; width <= n; width++){

        for(int l = 0; l+width-1 < n; l++){

            if(width == 1){
                dp[width%2][l] = height[l];
            } else {
                dp[width%2][l] = Math.min(dp[1-width%2][l], height[l+width-1]);                     
            }
            max = Math.max(max, dp[width%2][l] * width);   
        }
    }        
    return max;
}

Решение 3: используйте стек.

time: O (n), space: O (n)

Это решение сложно, и я узнал, как это сделать из описания без графиков и с графиками . Я предлагаю вам прочитать две ссылки, прежде чем читать мои объяснения ниже. Трудно объяснить без графиков, поэтому мои объяснения могут быть трудными.

Ниже приводятся мои объяснения:

1. Для каждого бара мы должны иметь возможность найти самый большой прямоугольник содержащий этот бар. Таким образом, самый большой из этих n прямоугольников - это то, что мы хотим.
2. Чтобы получить самый большой прямоугольник для определенного бара (скажем, bar [i], (i + 1) -й бар), нам просто нужно чтобы узнать самый большой интервал, который содержит этот бар. Мы знаем, что все полосы в этом интервале должны быть по крайней мере одинаковой высоты с баром [i]. Итак, если мы выясним, сколько последовательных столбцов с одинаковой высотой или выше находится слева от бара [i], и сколько последовательных столбцов с одинаковой высотой или выше находится прямо справа от панели [ i], мы будем знать длину интервала, который является шириной самого большого прямоугольника для бара [i].
3. Чтобы подсчитать количество последовательных столбцов с одинаковой высотой или более высоким значением на ближайшем слева от бара [i], нам нужно всего лишь найти ближайшую полосу слева, которая короче, чем полоса [i], потому что все полосы между этой полосой и баром [i] будут последовательно одинаковыми - или выше баров.
4. Мы используем стек, чтобы динамически отслеживать все левые столбцы, которые короче определенного бара. Другими словами, если мы переходим от первого бара к бару [i], когда мы просто приходим к бару [i] и не обновляем стек, стек должен хранить все бары, которые не выше бар [i -1], включая сам бар [i-1]. Мы сравниваем высоту bar [i] с каждым баром в стеке, пока не найдем ту, которая короче, чем bar [i], которая является самым коротким коротким баром. Если полоса [i] выше, чем все столбцы в стеке, это означает, что все столбцы слева от бара [i] выше, чем bar [i].
5. Мы можем сделать то же самое на правая сторона i-го бара. Тогда для бара [i] мы знаем, сколько баров находится в интервале.

   public int solution3(int[] height) {
   
       int n = height.length;
       if(n == 0) return 0;
   
       Stack<Integer> left = new Stack<Integer>();
       Stack<Integer> right = new Stack<Integer>();
   
       int[] width = new int[n];// widths of intervals.
       Arrays.fill(width, 1);// all intervals should at least be 1 unit wide.
   
       for(int i = 0; i < n; i++){
           // count # of consecutive higher bars on the left of the (i+1)th bar
           while(!left.isEmpty() && height[i] <= height[left.peek()]){
               // while there are bars stored in the stack, we check the bar on the top of the stack.
               left.pop();                
           }
   
           if(left.isEmpty()){
               // all elements on the left are larger than height[i].
               width[i] += i;
           } else {
               // bar[left.peek()] is the closest shorter bar.
               width[i] += i - left.peek() - 1;
           }
           left.push(i);
       }
   
       for (int i = n-1; i >=0; i--) {
   
           while(!right.isEmpty() && height[i] <= height[right.peek()]){                
               right.pop();                
           }
   
           if(right.isEmpty()){
               // all elements to the right are larger than height[i]
               width[i] += n - 1 - i;
           } else {
               width[i] += right.peek() - i - 1;
           }
           right.push(i);
       }
   
       int max = Integer.MIN_VALUE;
       for(int i = 0; i < n; i++){
           // find the maximum value of all rectangle areas.
           max = Math.max(max, width[i] * height[i]);
       }
   
       return max;
   }