day60

1、leetcode84 柱状图中的最大矩形

1. 思路【宫水三叶题解】

   • 最终矩形的高度必然取自某个heights[i]，因此我们可以枚举最终矩形的高度来做。
   • 问题转换为当使用某个heights[i]作为矩形高度时，该矩形所能取得的最大宽度为多少。
   • 假设我们能够预处理出 l 和 r 数组
     • l[i]代表位置 i 左边最近一个比其小的位置（初始值为 −1）
     • r[i]代表位置 i 右边最近一个比其小的位置（初始值为 n）
     • r[i] - l[i] - 1 则是以 heights[i] 作为矩形高度时所能取得的最大宽度。
   • 预处理 l 和 r 数组则是经典的「求最近一个比当前值大的位置」单调栈问题。

2. 代码

   class Solution {
       public int largestRectangleArea(int[] heights) {
           int len = heights.length;
           int res = 0;
           int[] l = new int[len];
           int[] r = new int[len];
           Arrays.fill(l,-1);
           Arrays.fill(r,len);
           Deque<Integer> dq = new ArrayDeque<>();
   
           for(int i=len-1; i>=0; i--) {
               while(!dq.isEmpty() && heights[dq.peekLast()]>heights[i] ) {
                   l[dq.pollLast()] = i;
               }
               dq.offerLast(i);
           }
   
           dq.clear();
   
           for(int i=0; i<len; i++) {
               while(!dq.isEmpty() && heights[dq.peekLast()]>heights[i] ) {
                   r[dq.pollLast()] = i;
               }
               dq.offerLast(i);
           }
   
   
           for(int i=0; i<len; i++) {
               res = Math.max(res, heights[i]*(r[i]-l[i]-1));
           }
   
           return res;
       }
   }