（leetcode算法题）84. 柱状图中最大的矩形 2334. 元素值大于变化阈值的子
https://i-blog.csdnimg.cn/direct/2748615630904037aa54e76512233288.png将这个题目举行转化，就能变成典范的单调栈的题目，
由于原题目中矩形的面积完全取决于此中最小矩形的高度，那么很容易想到遍历每个矩形，让每一个矩形都做一次最小矩形，看看其能够覆盖的最大宽度是多少，就能找到题目标答案。
进一步，对于第 i 号能够形成的矩形来说，我们可以将其分为两部分对待，其高度都是heights,
矩形的左半部分：宽度是从 i 开始往回数，大于或等于heights 的最大一连的区间长度
矩形的右半部分：宽度是从 i 开始今后数，大于或等于heights 的最大一连的区间长度
是不是想到901. 股票代价跨度 当时的情况了呢？但是与901差异的是，需要考虑从左遍历和从右遍历的两种情况举行相加
那么901利用了一个从栈底到栈顶单调递减栈作为辅助容器，资助得到小于等于当前位置的一连区间长度，这里天然可以利用一个从栈底到栈顶单调递增栈作为辅助容器，资助得到大于等于当前位置的一连区间长度
但是！！！！！！！！！！！！！！！！！！！！！！！！！！
这里需要留意更新矩形左右半部分的长度策略，我们以左半部分为例
由于接纳了单调递增栈，那么当遍历到heights 这个高度时，我们想要更新的到底是什么，策略有两种
策略一：找到大于等于heights 的且离 i 最远的 谁人下标，那么这个就是左半部分的端点
策略二：找到小于 heights 的且离 i 迩来的 谁人下标，加一就是左半部分的端点
如果将每更新一个端点就去遍历的方案视为错，那么这两种策略一对一错，读者不妨考虑一下哪个是对的？
~
~
~
~
公布答案，策略二是对的！
策略一的反例，对于 heights = 来说，在更新 heights = 4 这个点的左半部分的端点时，如果想用单调递增栈找到 6，这是不可能的，由于在更新heights = 5 时，这个已经把6pop出栈，此时要妄想利用记录6下标的逻辑的话，就是一个暴力遍历的过程，以是此时采用策略二：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
stack<int> st;
vector<int> recordleft(n, -1);
vector<int> recordright(n, n);
for(int i = 0; i < n; ++i){
/*利用从栈底到栈顶的单调递增栈更新*/
/*记录当前木板离他最近的那个小于当前木板高度的下标*/
while(!st.empty() && heights >= heights){
st.pop();
}
if(!st.empty()){
recordleft = st.top();
}
st.push(i);
}
st = stack<int> ();
for(int j = n - 1; j >= 0; --j){
while(!st.empty() && heights >= heights){
st.pop();
}
if(!st.empty()){
recordright = st.top();
}
st.push(j);
}
int ret = 0;
for(int i = 0; i < n; ++i){
int curlongestlen = recordright - recordleft - 1;
ret = max(ret, curlongestlen * heights);
}
return ret;
}
};
https://i-blog.csdnimg.cn/direct/f09ee51cba3747718bb6a10665dfdfd4.png
这里可以采用与84题相同的算法来更新，这是由于2334也可以转换成一个相同的题目：将nums作为一连子数组中最小的谁人数，更新出一连子数组的的长度 k，然后判定 nums / k 和threshold的关系
那么这个题和 84不是一模一样的两个题吗！！！
class Solution {
public:
int validSubarraySize(vector<int>& nums, int threshold) {
int n = nums.size();
stack<int> st;
// vector<int> biggestminsubnumthancurnuminleft(n);
vector<int> bmsntcinl(n);
for(int i = 0; i < n; ++i){
while(!st.empty() && nums >= nums){
st.pop();
}
if(!st.empty()){
bmsntcinl = st.top();
}
else{
bmsntcinl = -1;
}
st.push(i);
}
st = stack<int> ();
// vector<int> biggestminsubnumthancurnuminright(n);
vector<int> bmsntcinr(n);
for(int j = n - 1; j >= 0; --j){
while(!st.empty() && nums >= nums){
st.pop();
}
if(!st.empty()){
bmsntcinr = st.top();
}
else{
bmsntcinr = n;
}
st.push(j);
}
for(int i = 0; i < n; ++i){
int curk = bmsntcinr - bmsntcinl - 1;
// 在nums的从bmsntcinr + 1 到 bmsntcinl - 1的这些位置中
// 所有数都比nums大
if(nums > threshold / curk){
return curk;
}
}
return -1;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]