（leetcode算法题）84. 柱状图中最大的矩形 2334. 元素值大于变化阈值的子 ...

将这个题目举行转化，就能变成典范的单调栈的题目，
由于原题目中矩形的面积完全取决于此中最小矩形的高度，那么很容易想到遍历每个矩形，让每一个矩形都做一次最小矩形，看看其能够覆盖的最大宽度是多少，就能找到题目标答案。
进一步，对于第 i 号能够形成的矩形来说，我们可以将其分为两部分对待，其高度都是heights,
   矩形的左半部分：宽度是从 i 开始往回数，大于或等于heights 的最大一连的区间长度
  矩形的右半部分：宽度是从 i 开始今后数，大于或等于heights 的最大一连的区间长度
  是不是想到901. 股票代价跨度 当时的情况了呢？但是与901差异的是，需要考虑从左遍历和从右遍历的两种情况举行相加
那么901利用了一个从栈底到栈顶单调递减栈作为辅助容器，资助得到小于等于当前位置的一连区间长度，这里天然可以利用一个从栈底到栈顶单调递增栈作为辅助容器，资助得到大于等于当前位置的一连区间长度
但是！！！！！！！！！！！！！！！！！！！！！！！！！！
这里需要留意更新矩形左右半部分的长度策略，我们以左半部分为例
由于接纳了单调递增栈，那么当遍历到heights 这个高度时，我们想要更新的到底是什么，策略有两种
   策略一：找到大于等于heights 的且离 i  最远的  谁人下标，那么这个就是左半部分的端点
  策略二：找到小于 heights  的且离 i 迩来的 谁人下标，加一就是左半部分的端点
  如果将每更新一个端点就去遍历的方案视为错，那么这两种策略一对一错，读者不妨考虑一下哪个是对的？
~
~
~
~
公布答案，策略二是对的！
策略一的反例，对于 heights = [3,6,5,7,4,8,1,0] 来说，在更新 heights = 4 这个点的左半部分的端点时，如果想用单调递增栈找到 6，这是不可能的，由于在更新heights = 5 时，这个已经把6pop出栈，此时要妄想利用记录6下标的逻辑的话，就是一个暴力遍历的过程，以是此时采用策略二：

1. class Solution {
2. public:
3.     int largestRectangleArea(vector<int>& heights) {
4.         int n = heights.size();
5.         stack<int> st;
6.         vector<int> recordleft(n, -1);
7.         vector<int> recordright(n, n);
8.         for(int i = 0; i < n; ++i){
9. /*利用从栈底到栈顶的单调递增栈更新*/
10. /*记录当前木板离他最近的那个小于当前木板高度的下标*/
11.             while(!st.empty() && heights[st.top()] >= heights[i]){
12.                 st.pop();
13.             }
14.             if(!st.empty()){
15.                 recordleft[i] = st.top();
16.             }
17.             st.push(i);
18.         }
19.         st = stack<int> ();
20.         for(int j = n - 1; j >= 0; --j){
21.             while(!st.empty() && heights[st.top()] >= heights[j]){
22.                 st.pop();
23.             }
24.             if(!st.empty()){
25.                 recordright[j] = st.top();
26.             }
27.             st.push(j);           
28.         }
29.         int ret = 0;
30.         for(int i = 0; i < n; ++i){
31.             int curlongestlen = recordright[i] - recordleft[i] - 1;
32.             ret = max(ret, curlongestlen * heights[i]);
33.         }
34.         return ret;
35.     }
36. };

复制代码

这里可以采用与84题相同的算法来更新，这是由于2334也可以转换成一个相同的题目：将nums作为一连子数组中最小的谁人数，更新出一连子数组的的长度 k，然后判定 nums / k 和threshold的关系
那么这个题和 84不是一模一样的两个题吗！！！

1. class Solution {
2. public:
3.     int validSubarraySize(vector<int>& nums, int threshold) {
4.         int n = nums.size();
5.         stack<int> st;
6.         // vector<int> biggestminsubnumthancurnuminleft(n);
7.         vector<int> bmsntcinl(n);
8.         for(int i = 0; i < n; ++i){
9.             while(!st.empty() && nums[st.top()] >= nums[i]){
10.                 st.pop();
11.             }
12.             if(!st.empty()){
13.                 bmsntcinl[i] = st.top();
14.             }
15.             else{
16.                 bmsntcinl[i] = -1;
17.             }
18.             st.push(i);
19.         }
20.         st = stack<int> ();
21.         // vector<int> biggestminsubnumthancurnuminright(n);
22.         vector<int> bmsntcinr(n);
23.         for(int j = n - 1; j >= 0; --j){
24.             while(!st.empty() && nums[st.top()] >= nums[j]){
25.                 st.pop();
26.             }
27.             if(!st.empty()){
28.                 bmsntcinr[j] = st.top();
29.             }
30.             else{
31.                 bmsntcinr[j] = n;
32.             }
33.             st.push(j);
34.         }
36.         for(int i = 0; i < n; ++i){
37.             int curk = bmsntcinr[i] - bmsntcinl[i] - 1;
38.             // 在nums的从bmsntcinr[i] + 1 到 bmsntcinl[i] - 1的这些位置中
39.             // 所有数都比nums[i]大
40.             if(nums[i] > threshold / curk){
41.                 return curk;
42.             }
43.         }
44.         return -1;
45.     }
46. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。