Максимизируйте прямоугольную область под гистограммой

Question

У меня есть гистограмма с целочисленной высотой и постоянной шириной 1. Я хочу увеличить прямоугольную область под гистограммой. e.g.:

 _
| |
| |_ 
|   |
|   |_
|     |

Ответ на этот вопрос будет 6, 3 * 2, используя col1 и col2.

O (n ^ 2) грубая сила мне понятна, я бы хотел алгоритм O (n log n). Я пытаюсь думать о динамическом программировании по принципу максимально возрастающей подпоследовательности O (n log n), но не собираюсь идти вперед. Должен ли я использовать алгоритм «разделяй и властвуй»?

PS: Людям с достаточной репутацией предлагается удалить тег «разделяй и властвуй», если такого решения не существует.

После комментариев Мхо: я имею в виду площадь самого большого прямоугольника, которая полностью соответствует. (Спасибо j_random_hacker за разъяснения :)).

Answer 1

Приведенные выше ответы дали лучшее O (n) решение в коде, однако их объяснения довольно сложны для понимания. Алгоритм O (n), использующий стек, поначалу казался мне волшебным, но сейчас он имеет смысл для меня. ОК, позвольте мне объяснить это.

Первое наблюдение:

Чтобы найти максимальный прямоугольник, если для каждого бара x мы знаем первый меньший столбец с каждой стороны, скажем, l и r, мы уверены, что height[x] * (r - l - 1) - лучший выстрел можно получить, используя высоту бара x. На рисунке ниже 1 и 2 - первые меньшие из 5.

Хорошо, давайте предположим, что мы можем сделать это за O (1) время для каждого бара, затем мы можем решить эту проблему за O (n)! сканируя каждую полосу.

Тогда возникает вопрос: можем ли мы найти для каждого бара первый меньший бар слева и справа за O (1) раз? Это кажется невозможным, верно? ... Это возможно при использовании увеличивающегося стека.

Почему при использовании увеличивающегося стека можно отслеживать первый меньший слева и справа?

Возможно, сказать, что увеличивающийся стек может выполнять эту работу, совсем не убедительно, поэтому я проведу вас через это.

Во-первых, для увеличения стека нам понадобится одна операция:

while x < stack.top():
    stack.pop()
stack.push(x)

Затем вы можете проверить, что в увеличивающемся стеке (как показано ниже), для stack[x], stack[x-1] будет первым меньшим слева, затем новый элемент, который может выдвинуть stack[x], будет первым меньшим это право.

Все еще не могу поверить, что стек [x-1] является первым меньшим слева в стеке [x]?

Я докажу это противоречием.

Прежде всего, stack[x-1] < stack[x] точно. Но давайте предположим, что stack[x-1] не является первым меньшим слева от stack[x].

Так где же первый поменьше fs?

If fs < stack[x-1]:
    stack[x-1] will be popped out by fs,
else fs >= stack[x-1]:
    fs shall be pushed into stack,
Either case will result fs lie between stack[x-1] and stack[x], which is contradicting to the fact that there is no item between stack[x-1] and stack[x].

Поэтому стек [x-1] должен быть первым меньшим.

Резюме:

Увеличивающийся стек может отслеживать первый меньший слева и справа для каждого элемента. Используя это свойство, можно решить максимальный прямоугольник в гистограмме с помощью стека в O (n).

Поздравляем! Это действительно сложная проблема, я рад, что мое прозаическое объяснение не помешало вам закончить. Приложено мое проверенное решение в качестве вашей награды:)

def largestRectangleArea(A):
    ans = 0
    A = [-1] + A
    A.append(-1)
    n = len(A)
    stack = [0]  # store index

    for i in range(n):
        while A[i] < A[stack[-1]]:
            h = A[stack.pop()]
            area = h*(i-stack[-1]-1)
            ans = max(ans, area)
        stack.append(i)
    return ans

Answer 2

Существует три способа решения этой проблемы в дополнение к подходу грубой силы.Я запишу их все.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: использовать стек .

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

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

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

1. Для каждого бара мы должны быть в состоянии найти самый большойпрямоугольник, содержащий эту полосу.Поэтому самый большой из этих n прямоугольников - это то, что нам нужно.

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

3. Для подсчета количества последовательных одинаковых высот илиболее высокие столбцы слева от столбца [i], нам нужно только найти ближайший столбец слева, который короче столбца [i], потому что все столбцы между этим столбцом и столбцом [i] будут последовательно одинаковыми.бары высоты или выше.

4. Мы используем стек для динамического отслеживания всех левых столбцов, которые короче определенного столбца.Другими словами, если мы выполняем итерацию от первого бара до бара [i], когда мы просто достигаем бара [i] и не обновили стек, стек должен хранить все бары, которые не выше bar [i]-1], включая сам бар [i-1].Мы сравниваем высоту bar [i] с каждым баром в стеке, пока не найдем тот, который короче bar [i], который является самым коротким баром.Если столбец [i] выше, чем все столбцы в стеке, это означает, что все столбцы слева от столбца [i] выше, чем столбец [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;
   }
   

Answer 3

Реализация в Python ответ @ IVlad O (n) решение:

from collections import namedtuple

Info = namedtuple('Info', 'start height')

def max_rectangle_area(histogram):
    """Find the area of the largest rectangle that fits entirely under
    the histogram.

    """
    stack = []
    top = lambda: stack[-1]
    max_area = 0
    pos = 0 # current position in the histogram
    for pos, height in enumerate(histogram):
        start = pos # position where rectangle starts
        while True:
            if not stack or height > top().height:
                stack.append(Info(start, height)) # push
            elif stack and height < top().height:
                max_area = max(max_area, top().height*(pos-top().start))
                start, _ = stack.pop()
                continue
            break # height == top().height goes here

    pos += 1
    for start, height in stack:
        max_area = max(max_area, height*(pos-start))

    return max_area

Пример:

>>> f = max_rectangle_area
>>> f([5,3,1])
6
>>> f([1,3,5])
6
>>> f([3,1,5])
5
>>> f([4,8,3,2,0])
9
>>> f([4,8,3,1,1,0])
9

Линейный поиск с использованиемстек неполных подзадач

Описание алгоритма копирования-вставки (в случае, если страница откроется):

Мы обрабатываем элементы в порядке слева направо и поддерживаемстопка информации о запущенных, но еще не завершенных подгистограммах.Каждый раз, когда появляется новый элемент, он подчиняется следующим правилам.Если стек пуст, мы открываем новую подзадачу, помещая элемент в стек.В противном случае мы сравниваем его с элементом на вершине стека.Если новый больше, мы снова подталкиваем его.Если новый равен, мы пропускаем его.Во всех этих случаях мы переходим к следующему новому элементу.Если новый меньше, мы заканчиваем самую верхнюю подзадачу, обновляя максимальную площадь относительно элемента в верхней части стека.Затем мы отбрасываем элемент сверху и повторяем процедуру, сохраняя текущий новый элемент.Таким образом, все подзадачи завершаются, пока стек не станет пустым, или его верхний элемент не станет меньше или равен новому элементу, что приведет к действиям, описанным выше.Если все элементы были обработаны, а стек еще не пуст, мы заканчиваем оставшиеся подзадачи, обновляя максимальную площадь по отношению к элементам вверху.

Для обновления по элементу мы находим наибольшеепрямоугольник, который включает этот элемент.Обратите внимание, что обновление максимальной площади выполняется для всех элементов, кроме пропущенных.Однако, если элемент пропущен, он имеет тот же самый большой прямоугольник, что и элемент в верхней части стека, который будет обновлен позже.Высота самого большого прямоугольника - это, конечно, значение элемента.Во время обновления мы знаем, как далеко простирается самый большой прямоугольник справа от элемента, потому что тогда впервые появился новый элемент с меньшей высотой.Информация о том, как далеко самый большой прямоугольник простирается слева от элемента, доступна, если мы также сохраним его в стеке.

Поэтому мы пересматриваем процедуру, описанную выше.Если новый элемент перемещается немедленно, либо потому, что стек пуст, либо он больше верхнего элемента стека, самый большой прямоугольник, содержащий его, расширяется влево не дальше, чем текущий элемент.Если он выталкивается после выталкивания нескольких элементов из стека, поскольку он меньше, чем эти элементы, самый большой прямоугольник, в котором он находится, простирается влево до прямоугольника самого последнего вытолкнутого элемента.

Каждый элементтолкается и выталкивается максимум один раз, и на каждом этапе процедуры толкается или выталкивается хотя бы один элемент.Поскольку объем работ по принятию решений и обновлению постоянен, сложность алгоритма по амортизированному анализу составляет O (n).

Answer 4

Другие ответы здесь проделали большую работу, представив решение O (n) -время, O (n) -пространстве с использованием двух стеков. Есть еще одна точка зрения на эту проблему, которая независимо обеспечивает решение проблемы в O (n) -времени, O (n) -пространстве и может дать немного больше понимания того, почему работает решение на основе стека.

Ключевой идеей является использование структуры данных, называемой декартовым деревом . Декартово дерево - это двоичная древовидная структура (но не бинарное дерево search ), построенная вокруг входного массива. В частности, корень декартового дерева строится над минимальным элементом массива, а левое и правое поддеревья рекурсивно строятся из подмассивов слева и справа от минимального значения.

Например, вот примерный массив и его декартово дерево:

                 +----------------------- 23 ------+
                 |                                 |
  +------------- 26 --+                        +-- 79
  |                   |                        |
  31 --+              53 --+                   84
       |                   |
       41 --+              58 -------+
            |                        |
            59                  +-- 93
                                |
                                97

+----+----+----+----+----+----+----+----+----+----+----+
| 31 | 41 | 59 | 26 | 53 | 58 | 97 | 93 | 23 | 84 | 79 |
+----+----+----+----+----+----+----+----+----+----+----+

Причина, по которой картезианские деревья полезны в этой задаче, заключается в том, что рассматриваемый вопрос имеет действительно хорошую рекурсивную структуру. Начните с просмотра самого нижнего прямоугольника на гистограмме. Есть три варианта, где может располагаться максимальный прямоугольник:

• Может проходить прямо под минимальным значением в гистограмме. В этом случае, чтобы сделать его максимально большим, мы бы хотели сделать его таким же широким, как весь массив.

• Может быть полностью слева от минимального значения. В этом случае мы рекурсивно хотим, чтобы ответ формировался из подмассива только слева от минимального значения.

• Может быть полностью справа от минимального значения. В этом случае мы рекурсивно хотим, чтобы ответ формировался из подмассива чисто справа от минимального значения.

Обратите внимание, что эта рекурсивная структура - найдите минимальное значение, сделайте что-нибудь с подрешетками слева и справа от этого значения - идеально соответствует рекурсивной структуре декартового дерева. Фактически, если мы сможем создать декартово дерево для всего массива, когда мы начнем, мы сможем решить эту проблему, рекурсивно пройдя декартово дерево от корня вниз. В каждой точке мы рекурсивно вычисляем оптимальный прямоугольник в левом и правом подрешетках вместе с прямоугольником, который вы получите, подгоняя справа под минимальным значением, и затем возвращаете лучший вариант, который мы находим.

В псевдокоде это выглядит так:

function largestRectangleUnder(int low, int high, Node root) {
  /* Base case: If the range is empty, the biggest rectangle we
   * can fit is the empty rectangle.
   */
  if (low == high) return 0;

  /* Assume the Cartesian tree nodes are annotated with their
   * positions in the original array.
   */
  return max {
    (high - low) * root.value, // Widest rectangle under the minimum
    largestRectangleUnder(low,            root.index, root.left),
    largestRectnagleUnder(root.index + 1, high,       root.right)
  }
}

Когда у нас есть декартово дерево, этот алгоритм занимает время O (n), поскольку мы посещаем каждый узел ровно один раз и выполняем O (1) работу на узел.

Оказывается, существует простой линейный алгоритм построения декартовых деревьев. «Естественный» способ, которым вы, вероятно, подумаете построить его, будет сканировать массив, найти минимальное значение, а затем рекурсивно построить декартово дерево из левого и правого подмассивов. Проблема в том, что процесс поиска минимального значения действительно дорог, и это может занять время & theta; (n ² ).

«Быстрый» способ построить декартово дерево - это сканировать массив слева направо, добавляя по одному элементу за раз. Этот алгоритм основан на следующих наблюдениях о декартовых деревьях:

• Во-первых, декартовы деревья подчиняются свойству кучи: каждый элемент меньше или равен своим дочерним элементам. Причина этого заключается в том, что корень декартового дерева является наименьшим значением в общем массиве, а его дочерние элементы - наименьшими элементами в их подмассивах и т. Д.

• Во-вторых, если вы выполняете обход по порядку декартового дерева, вы возвращаете элементы массива в порядке их появления. Чтобы понять, почему это так, обратите внимание, что если вы выполняете обход по декартовому дереву по порядку, сначала вы просматриваете все слева от минимального значения, затем минимальное значение, затем все справа от минимального значения. Эти посещения рекурсивно выполняются таким же образом, поэтому все заканчивается посещением по порядку.

Эти два правила дают нам много информации о том, что произойдет, если мы начнем с декартового дерева первых k элементов массива и захотим сформировать декартово дерево для первых k + 1 элементов.Этот новый элемент должен в конечном итоге оказаться в правом позвоночнике декартового дерева - части дерева, образованной путем начала у корня и принятия шагов только вправо - потому что в противном случае что-то последует за ним в обходе по порядку.И внутри этого правого отдела позвоночника его нужно разместить таким образом, чтобы он был больше, чем все, что находится над ним, поскольку нам нужно подчиняться свойству кучи.

Способ, которым вы фактически добавляете новый узел кДекартово дерево должно начинаться с самого правого узла дерева и идти вверх до тех пор, пока вы не коснетесь корня дерева или не найдете узел с меньшим значением.Затем вы делаете новое значение своим левым потомком, последним узлом, на котором оно поднялось.

Вот след этого алгоритма на небольшом массиве:

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

2 становится корнем.

  2 --+
      |  
      4

4 больше 2, мы не можем двигаться вверх.Добавить справа.

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

  2 ------+
          |
      --- 3 
      |
      4

3 меньше 4, перелезть через него.Не может подняться дальше, чем на 2, так как оно меньше, чем 3. Поднявшись по поддереву с корнем в 4, идет слева от нового значения 3, и теперь 3 становится самым правым узлом.

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

  +---------- 1
  |
  2 ------+
          |
      --- 3
      |
      4

1 поднимается над корнем 2, все дерево с корнем в 2 перемещается влево от 1, и теперь 1 - это новый корень, а также крайнее правое значение.

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

Хотя это можетне кажется, что он бежит по линейному времени - разве вы не могли бы в конечном итоге взбираться на корни дерева снова и снова и снова?- вы можете показать, что это работает за линейное время, используя умный аргумент.Если вы поднимаетесь над узлом в правом позвоночнике во время вставки, этот узел в конечном итоге смещается с правого отдела позвоночника и поэтому не может быть повторно отсканирован в следующей вставке.Таким образом, каждый узел сканируется только один раз, поэтому общая выполняемая работа является линейной.

А теперь главное - стандартным способом, которым вы фактически реализуете этот подход, является поддержание стеказначения, которые соответствуют узлам на правом позвоночнике.Акт «поднятия» вверх по узлу соответствует выталкиванию узла из стека.Поэтому код для построения декартового дерева выглядит примерно так:

Stack s;
for (each array element x) {
   pop s until it's empty or s.top > x
   push x onto the stack.
   do some sort of pointer rewiring based on what you just did.

Вот некоторый Java-код, который реализует эту идею, благодаря @Azeem!

import java.util.Stack;

public class CartesianTreeMakerUtil {

    private static class Node {
        int val;
        Node left;
        Node right;
    }

    public static Node cartesianTreeFor(int[] nums) {
        Node root = null;
        Stack<Node> s = new Stack<>();
        for(int curr : nums) {
            Node lastJumpedOver = null;
            while(!s.empty() && s.peek().val > curr) {
                lastJumpedOver = s.pop();
            }
            Node currNode = this.new Node();
            currNode.val = curr;
            if(s.isEmpty()) {
                root = currNode;
            }
            else {
                s.peek().right = currNode;
            }
            currNode.left = lastJumpedOver;
            s.push(currNode);
        }
        return root;
    }

    public static void printInOrder(Node root) {
        if(root == null) return;
        if(root.left != null ) {
            printInOrder(root.left);
        }
        System.out.println(root.val);
        if(root.right != null) {
            printInOrder(root.right);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[args.length];
        for (int i = 0; i < args.length; i++) {
            nums[i] = Integer.parseInt(args[i]);
        }
        Node root = cartesianTreeFor(nums);
        tester.printInOrder(root);
    }
}

Манипуляции со стеком здесьможет показаться очень знакомым, и это потому, что это именно те операции стека, которые вы выполняете в ответах, показанных в другом месте здесь. На самом деле, вы можете думать о том, что эти подходы делают как неявно 1091* построение декартового дерева и запуск рекурсивного алгоритма, показанного выше, в процессе этого.

Преимущество знания о декартовых деревьях, я думаю, состоит в том, что оно обеспечивает действительно хорошую концептуальную основу для понимания, почему этот алгоритмработает правильно.Если вы знаете, что вы выполняете рекурсивный обход декартового дерева, легче увидеть, что вы гарантированно найдете самый большой прямоугольник.Кроме того, знание того, что декартово дерево существует, дает вам полезный инструмент для решения других проблем.Декартовы деревья обнаруживаются при проектировании быстрых структур данных для задачи минимального запроса в диапазоне и используются для преобразования массивов суффиксов в деревья суффиксов .

Answer 5

Самое простое решение в O (N)

long long getMaxArea(long long hist[], long long n)
{

    stack<long long> s;

    long long max_area = 0; 
    long long tp;  
    long long area_with_top; 

    long long i = 0;
    while (i < n)
    {
        if (s.empty() || hist[s.top()] <= hist[i])
            s.push(i++);
       else
        {
            tp = s.top();  // store the top index
            s.pop();  // pop the top
            area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
            if (max_area < area_with_top)
            {
                max_area = area_with_top;
            }
        }
    }

   while (!s.empty())
    {
        tp = s.top();
        s.pop();
        area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);

        if (max_area < area_with_top)
            max_area = area_with_top;
    }

    return max_area;
}

Answer 6

Стековое решение - одно из самых умных решений, которые я когда-либо видел.И может быть немного трудно понять, почему это работает.

Я попытался объяснить то же самое в некоторых деталях здесь .

Краткие сведения из поста: -

• Общий способ мышления нашего мозга таков: -
  • Создайте каждую ситуацию и попытайтесь найти значение противопоказания, необходимого для решения проблемы.
  • И мы с радостью преобразуем этозакодировать как: - найти значение контраргумента (мин) для каждой ситуации (пара (i, j))

Умные решения пытаются перевернуть проблему. Для каждого constraint/min значения области, каковы наилучшие возможные крайние значения слева и справа?

• Так что, если мы пройдемся по каждому возможному min в массиве.Каковы крайние значения слева и справа для каждого значения?

  • Немного подумав, первое самое левое значение меньше current min и аналогично первое крайнее правое значение меньше текущего минимума.

• Итак, теперь нам нужно посмотреть, найдем ли мы умный способ найти первые левые и правые значения, меньшие, чем текущее значение.

• Думать : Если мы обошли массив частично, скажем, до min_i, как можно построить решение для min_i + 1?

• Нам нужен первыйзначение меньше, чем min_i слева от него.

• Инвертирование оператора: нам нужно игнорировать все значения слева от min_i, которые больше, чем min_i.Мы останавливаемся, когда находим первое значение меньше min_i (i). Следовательно, впадины на кривой становятся бесполезными, когда мы пересекаем ее .На гистограмме (2 4 3) => если 3 равно min_i, то увеличение 4 не представляет интереса.
• Следствие : в диапазоне (i, j).j - это минимальное значение, которое мы рассматриваем ... все значения между j и его левым значением i бесполезны.Даже для дальнейших расчетов.
• Любая гистограмма справа с минимальным значением, большим, чем j, будет связана в j.Интересующие значения слева образуют монотонно возрастающую последовательность с j, являющимся наибольшим значением.(Интересующие значения здесь являются возможными значениями, которые могут представлять интерес для более позднего массива)
• Поскольку мы перемещаемся слева направо, для каждого минимального значения / текущего значения - мы не знаем, находится ли правая сторонамассива будет иметь элемент меньше его.
  • Поэтому мы должны хранить его в памяти, пока не узнаем, что это значение бесполезно.(поскольку найдено меньшее значение)

• Все это приводит к использованию нашей собственной stack структуры.

  • Мы продолжаемстека, пока мы не знаем, его бесполезно.
  • Мы удаляем из стека, как только мы знаем, что это дерьмо.

• Так что для каждого минимального значения, чтобы найтиПри меньшем левом значении мы делаем следующее: -

  1. выталкиваем элементы, которые больше по нему (бесполезные значения)
  2. Первый элемент, меньший значения, является левым крайним.I к нашему мин.
• Мы можем сделать то же самое с правой стороны массива, и мы получим j к нашему мин.

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

Answer 7

Существует также другое решение, использующее Разделяй и властвуй.Алгоритм для этого:

1) Разделить массив на 2 части с наименьшей высотой в качестве точки разрыва

2) Максимальная площадь - максимум: а) Наименьшая высота * размермассива б) Максимальный прямоугольник в левой половине массива в) Максимальный прямоугольник в правой половине массива

Сложность по времени доходит до O (nlogn)

Answer 8

Я хотел бы поблагодарить @templatetypedef за его чрезвычайно подробный и интуитивно понятный ответ.Приведенный ниже код Java основан на его предложении использовать декартовы деревья и решает проблему в O (N) времени и O (N) пространстве.Я предлагаю вам прочитать ответ @ templatetypedef выше, прежде чем читать код ниже.Код дается в формате решения проблемы на leetcode: https://leetcode.com/problems/largest-rectangle-in-histogram/description/ и проходит все 96 тестовых случаев.

class Solution {

private class Node {
    int val;
    Node left;
    Node right;
    int index;
}

public  Node getCartesianTreeFromArray(int [] nums) {
    Node root = null;
    Stack<Node> s = new Stack<>();
    for(int i = 0; i < nums.length; i++) {
        int curr = nums[i];
        Node lastJumpedOver = null;
        while(!s.empty() && s.peek().val >= curr) {
            lastJumpedOver = s.pop();
        }
        Node currNode = this.new Node();
        currNode.val = curr;
        currNode.index = i;
        if(s.isEmpty()) {
            root = currNode;
        }
        else {
            s.peek().right = currNode;
        }
        currNode.left = lastJumpedOver;
        s.push(currNode);
    }
    return root;
}

public int largestRectangleUnder(int low, int high, Node root, int [] nums) {
    /* Base case: If the range is empty, the biggest rectangle we
     * can fit is the empty rectangle.
     */
    if(root == null) return 0;

    if (low == high) {
        if(0 <= low && low <= nums.length - 1) {
            return nums[low];
        }
        return 0;
    }

    /* Assume the Cartesian tree nodes are annotated with their
     * positions in the original array.
     */
    int leftArea = -1 , rightArea= -1;
    if(root.left != null) {
        leftArea = largestRectangleUnder(low, root.index - 1 , root.left, nums);
    }
    if(root.right != null) {
        rightArea = largestRectangleUnder(root.index + 1, high,root.right, nums);
    }
    return Math.max((high - low  + 1) * root.val, 
           Math.max(leftArea, rightArea));
}

public int largestRectangleArea(int[] heights) {
    if(heights == null || heights.length == 0 ) {
        return 0;
    }
    if(heights.length == 1) {
        return heights[0];
    }
    Node root = getCartesianTreeFromArray(heights);
    return largestRectangleUnder(0, heights.length - 1, root, heights);
}

}

Answer 9

Я кодировал это и чувствовал себя немного лучше в смысле:

import java.util.Stack;

     class StackItem{
       public int sup;
       public int height;
       public int sub;

       public StackItem(int a, int b, int c){
           sup = a;
           height = b;
           sub =c;
       }
       public int getArea(){
           return (sup - sub)* height;
       }


       @Override
       public String toString(){
       return "     from:"+sup+
              "     to:"+sub+
              "     height:"+height+              
              "     Area ="+getArea();
       }
    }   


public class MaxRectangleInHistogram {    
    Stack<StackItem> S;
    StackItem curr;
    StackItem maxRectangle;

    public StackItem getMaxRectangleInHistogram(int A[], int n){
        int i = 0;
        S = new Stack();        
        S.push(new StackItem(0,0,-1));
        maxRectangle = new StackItem(0,0,-1);

        while(i<n){

                curr = new StackItem(i,A[i],i);

                    if(curr.height > S.peek().height){
                            S.push(curr); 
                    }else if(curr.height == S.peek().height){                            
                            S.peek().sup = i+1;                         
                    }else if(curr.height < S.peek().height){                            

                            while((S.size()>1) && (curr.height<=S.peek().height)){
                                curr.sub = S.peek().sub;
                                S.peek().sup = i;
                                decideMaxRectangle(S.peek());
                                S.pop(); 
                            }                               
                        S.push(curr);                    
                    }
            i++;
        }

        while(S.size()>1){ 
            S.peek().sup = i;
            decideMaxRectangle(S.peek());
            S.pop();            
        }  

        return maxRectangle;
    }

    private void decideMaxRectangle(StackItem s){ 

        if(s.getArea() > maxRectangle.getArea() )
            maxRectangle = s;      
    }

}

Просто обратите внимание:

Time Complexity: T(n) < O(2n) ~ O(n)
Space Complexity S(n) < O(n)

Answer 10

Я не понимаю другие записи, но я думаю, что знаю, как сделать это в O (n) следующим образом.

A) для каждого индекса найдите самый большой прямоугольник внутри гистограммы, заканчивающийся на этоминдекс, где столбец индекса касается верхней части прямоугольника и запоминает, где начинается прямоугольник.Это можно сделать в O (n) с использованием стекового алгоритма.

B) Аналогично для каждого индекса найдите самый большой прямоугольник, начинающийся с этого индекса, где столбец индекса касается верхней части прямоугольника, и запомните, где находится прямоугольникзаканчивается.Также O (n), используя тот же метод, что и (A), но сканируя гистограмму в обратном направлении.

C) Для каждого индекса объедините результаты (A) и (B), чтобы определить самый большой прямоугольник, где столбец находится вэтот индекс касается верхней части прямоугольника.O (n) like (A).

D) Поскольку какой-либо столбец гистограммы должен касаться самого большого прямоугольника, самый большой прямоугольник - это самый большой прямоугольник, найденный на шаге (C).

Сложная часть заключается в реализации (A) и (B), что, как мне кажется, решило Дж. Ф. Себастьян, а не заявленная общая проблема.