代码随想录算法训练营第60天|84.柱状图中最大的矩形

链接: 84.柱状图中最大的矩形

84.柱状图中最大的矩形

这道题为单调递减的单调栈文章来源地址https://uudwc.com/A/V6zXJ

class Solution {
    public int largestRectangleArea(int[] heights) {
            int res = 0;
            Stack<Integer> stack = new Stack<>();
            stack.push(0);  
            // 首尾添0
            int[] newH = new int[heights.length + 2];
            newH[0] = 0;
            newH[newH.length - 1] = 0;
            System.arraycopy(heights, 0, newH, 1, heights.length);

            for(int i = 1; i < newH.length; i++){
                if(newH[i] > newH[stack.peek()]){
                    stack.push(i);
                }else if(newH[i] == newH[stack.peek()]){
                    stack.pop();
                    stack.push(i);
                }else{
                    while(!stack.isEmpty() && newH[i] < newH[stack.peek()]){
                        int mid = stack.pop();
                        if(!stack.isEmpty()){
                            int left = stack.peek();
                            int right = i;
                            int w = right - left -1;
                            int h = newH[mid];
                            res = Math.max(res, w*h);
                        }
                    }
                    stack.push(i);
                }
                
            }
            return res;
    }
}