84. Largest Rectangle in Histogram ( mono increasing stack

https://leetcode.com/problems/largest-rectangle-in-histogram/

naive

T: O(n^2)

// 第二想到固定某柱子, 背向雙指針, 找左右邊界(找比自己高的), 求面積
class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int n = heights.length;
        for (int i = 0; i < n ; i++) {
            int curr = heights[i];
            int left = i-1;
            int right = i+1;
            while (left >= 0 && heights[left] >= curr) {
                left--;
            }
            while (right < n && heights[right] >= curr) {
                right++;
            }
            max = Math.max(max, curr*(right - left - 1));
        }
        return max;
    }
}

mono stack

h = heights[stack.pop()]; => 7

2 - 0 - 1

i - stack.peek() - 1

area = 7 * (2 - 0 - 1)

while (!stack.isEmpty() && heights[stack.peek()] >= cur) { // find right bound
    int h = heights[stack.pop()]; // one by one pop to use height to cal the area
    int w = stack.isEmpty() ? i : i - stack.peek() - 1; // 2 - 0 - 1
    ans = Math.max(ans, h * w);
} 

O(n), O(n)

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        
        int ans = 0;
        for (int i = 0; i <= heights.length; i++) {
            int cur = (i == heights.length) ? -1 : heights[i];
            
            while (!stack.isEmpty() && heights[stack.peek()] >= cur) { // find right bound
                int h = heights[stack.pop()]; // one by one pop to use height to cal the area
                int w = stack.isEmpty() ? i : i - stack.peek() - 1; // 2 - 0 - 1
                ans = Math.max(ans, h * w);
            } 
            stack.push(i);
        }
        return ans;
    }
}

readable version

i = heights.lenght , cur 設定成 -1, 用意在讓stack剩下的 pop()完(退棧）

heights[stack.peek()] >= cur => 一定 >= -1,

stack 空的時候, leftBound = -1, or stack.peek()

這樣才能算到比較低的那根到左邊界所有的面積

int rightBound = i;
int leftBound = stack.isEmpty() ? -1 : stack.peek();

2. 2

1

2會先退掉 (1比較小

2

1

到底才開始退(右邊界-1了

2退掉

1退掉, 此時stack 空了, 代表可以算左邊界 -1了

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
    
        // stack to record index,
        // for i = 0 ~ heights.length
        // while cur >= peek(), means find right bound = i, 
        // so pop h, get w, 
        // if stack is empty, means left bound is -1, or left bound is stack.peek()
        // cal area
        // push
        
        int max = 0;
        for (int i = 0; i <= heights.length; i++) {
            int cur = (i == heights.length) ? -1 : heights[i];
            
            while (!stack.isEmpty() && heights[stack.peek()] >= cur) {
                int h = heights[stack.pop()];
                int rightBound = i;
                int leftBound = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max, h*(rightBound - leftBound - 1));
            }
            stack.push(i);
        }
        return max;
    }
}

newest version

class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        int max = Integer.MIN_VALUE;
        // 因為是要左邊界右邊界, 所以要執行到 height的尾巴  i <= heights.length
        for (int i = 0; i <= heights.length; i++) { // why <= heights.length
            int curr = (i == heights.length) ? -1 : heights[i];
            
            while (!stack.isEmpty() && curr <= heights[stack.peek()]) {
                int h = heights[stack.pop()];
                int rightBound = i;
                int leftBound = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max, h*(rightBound - leftBound - 1));
            }
            stack.push(i);
        }
        return max;
    }
}