剑指 Offer II 039. 直方图最大矩形面积

剑指 Offer II 039. 直方图最大矩形面积

leetcode 上好像可以直接两重循环查找不会超时。

做cf的时候做到了相似题 顺手把leetcode这道题写了。

一下给出单调栈的优化代码

思路：单调栈进行存储每个加入元素的val，和index 。

当遇到比它小的值直接d出，再贪心记录 面积

1.当当前遍历值 a[i] >= 栈顶元素,直接将 压入栈

2. 当当前遍历值 a[i] < 栈顶元素时,将栈顶元素弹出,并记录:
   a n s = m a x ( a n s , v a l ∗ ( i − i n d e x ) ) ans = max(ans , val * (i - index)) ans=max(ans,val∗(i−index))

找到最后d出的index 作为 当前值得index, 压入栈

3.最后一步,不要忘记清空栈内元素.

class Solution {
    public int largestRectangleArea(int[] a) {    
        Deque<int[]> q = new LinkedList<>();
        q.offer(new int[]{a[0],0});
        int ans = 0;
        for(int i = 1; i < a.length;i++){
                if(!q.isEmpty() && q.peek()[0] > a[i]){
                    int[] h = q.peek();
                    while(!q.isEmpty() && q.peek()[0]>a[i]){  //  d出栈顶元素
                        h = q.poll();
                        ans = Math.max(h[0]*(i-h[1]),ans);
                    }
                    q.push(new int[]{a[i],h[1]}); //  这一步很重要,找到最后d出的index 作为 当前值得index, 压入栈
                }else{
                    q.push(new int[]{a[i],i});
                }
            }
        int[] h;
        while(!q.isEmpty()){
            h = q.poll();
            ans = Math.max(h[0]*(a.length-h[1]),ans);
        }
        return ans;
    }
}