84. Largest Rectangle in Histogram

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Solution:

class Solution {
    public int largestRectangleArea(int[] heights) {
        // Assumptions: array is not null, array.length >= 1,
        // all the values in the array are non-negativ.
        int result = 0;
        // Note that the stack contains the "index",
        // not the "value" of the array
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i <= heights.length; i++){
            // we need a way of popping out all the elements in the stack
            // at last, so that we explicitly add a bar of height 0.
            int cur;
            if (i == heights.length){
                cur = 0;
            }else{
                cur = heights[i];
            }

            while(!stack.isEmpty() && heights[stack.peekFirst()] >= cur){
                int height = heights[stack.pollFirst()];
                // determine the left boundary of the largest rectangle
                // with height array[i].
                int left;
                if (stack.isEmpty()){
                    left = 0;
                }else{
                    left = stack.peekFirst() + 1;
                }
                // determine the right boundary of the largest rectangle
                // with height of the popped element
                result = Math.max(result, height * (i - left));
            }
            stack.offerFirst(i);
        }
        return result;
    }
}
// TC: O(n) 算法的时间复杂度为O(n)，因为每个条形最多被压入栈和弹出栈一次。
// SC: O(n)

class Solution {
    public int largestRectangleArea(int[] heights) {
        int result = 0;
        // 0 1 2 3 4 5 
        /* 2,1,5,6,2,3 */
        //           i
        // cur

        /*
        stack:  6
         */

        Deque<Integer> stack = new LinkedList<Integer>();

        for (int i = 0; i <= heights.length; i++){
            int cur; // 2 // 1 // 5 // 6 // 2  // 3 // 0

            if (i == heights.length){
                cur = 0;
            }else{
                cur = heights[i];
            }

            // heights[0] = 2 >= 1 
            // heights[1] = 1 !>= 5

            // heights[2] = 5 !>= 6

            // heights[3] = 6 >= 2
            // heights[2] = 5 >= 2

            // heights[4] = 2 !>= 3

            // heights[5] = 3 >= 0

            // heights[4] = 2 >= 0

            // heithts[1] = 1 >=0

            while(!stack.isEmpty() && heights[stack.peekFirst()] >= cur){
                int height = heights[stack.pollFirst()];
                // height = 6 // 5
                // height = 3 
                // height =2 
                int left;
                if (stack.isEmpty()){
                    left = 0; 
                }else{
                    left = stack.peekFirst() + 1;
                    // left = 2 + 1 = 3 
                    // left = 1 + 1 =2 

                    // left = 4 + 1 = 5

                    // left = 1+1 =2 
                }

                result = Math.max(result, height * (i - left));
                // 0, 2 * (1 - 0) 
                // 0, 2 
                // (2, 6 * (4 - 3))
                // (2, 6 *1 )

                // (6, 5 * (4 - 2 ))
                //  (6, 10) = 10

                // (10, 3 * (6 - 5) ) = 10


                // (10, 2 * (6 - 2) = 8) = 10
                // (10, 1 * (6 - 0) = 6) = 10
            }

            stack.offerFirst(i);

            // 
        }

        return result; // 10
    }
}