小说网站开发源码,网站展示效果图,网站推广究竟应该怎么做,如何看网站的建站时间503.下一个更大元素II 与496.下一个更大元素 I的不同是要循环地搜索元素的下一个更大的数。那么主要是对于遍历结束后#xff0c;单调栈里面剩下的那些元素。 如果直接把两个数组拼接在一起#xff0c;然后使用单调栈求下一个最大值就可以。 代码实现的话#xff0c;不用直… 503.下一个更大元素II 与496.下一个更大元素 I的不同是要循环地搜索元素的下一个更大的数。那么主要是对于遍历结束后单调栈里面剩下的那些元素。 如果直接把两个数组拼接在一起然后使用单调栈求下一个最大值就可以。 代码实现的话不用直接把数组后面再接一个数组而是单调栈走2遍这个数组即可。 代码如下。第二次遍历使用取余的方法。 class Solution {
public:vectorint nextGreaterElements(vectorint nums) {int nnums.size();vectorint result(n,-1);stackint st;for(int i0;i2*n;i){int ki%n;while(!st.empty() nums[k]nums[st.top()]){result[st.top()]nums[k];st.pop();}st.push(k);}return result;}
}; 42. 接雨水 依据列来计算更好理解能引入单调栈可以看出因为左侧最高柱子和右侧最高柱子肯定不会存储雨水左侧和右侧包含自己因为自己是一侧最高的话不会存储雨水所以每一列雨水的高度取决于该列 左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。 下面图片以柱子4为例可以看见中间所有柱子都满足这个结论最两边的柱子不会存储雨水。 转化问题后有3种办法解决 会超时的暴力解法。双指针优化。重点的单调栈。 1、暴力解法。 对于每个元素都从左、从右找最大高度的柱子lheight、rheight所以外层循环是0到n-1内层循环从i往左然后从i往右找最大高度的柱子lheight、rheight最多会查找n次。所以时间复杂度是O(n^2)空间复杂度O(1)。但是会超时。 2、双指针优化。 当前元素的左边、右边最大高度的柱子lheight、rheight其实跟前一个元素的lheight、rheight有关。注意左边最大和右边最大要把自己考虑进去如果不包含左边最大/右边最大的可能比自己还小那么相减是负数最终结果比正确结果小。 当前i的lheight取决于左边i-1的lheightrheight取决于右边i1的rheight。具体如下 当前i的lheightmax(前一个lheightheight[i])所以需要从左到右得到lheight。 那么参照lheight当前i的rheight应该max(后一个lheightheight[i])与上面相反从右到左得到。 根据这个过程先把所有元素的lheight数组和rheight数组求出来然后再遍历元素的时候直接就是min(lheight[i],rheight[i])-height[i]。时间复杂度是O(n)空间复杂度O(n)。 代码如下。 class Solution {
public:int trap(vectorint height) {int nheight.size();int l1,r1,l2,r2;int count0;vectorint lheight(n);vectorint rheight(n);//初始化lheight[0]height[0];rheight[n-1]height[n-1];for(int i1;in-1;i){//中间元素的lheight和rheightlheight[i]max(lheight[i-1],height[i]);rheight[i]max(rheight[i1],height[i]);}for(int in-2;i0;--i){rheight[i]max(rheight[i1],height[i]);}for(int i0;in;i){if(i0 || in-1)continue;int curmin(lheight[i],rheight[i])-height[i];countcur;}return count;}
}; 上面的1、2都是按照列的方式去装水因为是找左右两边最大元素。 3、单调栈 如果按行装水的话就可以通过下一个更大元素和上一个最大元素来求。 以上图为例下标2左边更大是1右边更大是2所以自己这行以下标2柱高0为底以min(左边更大值右边更大值)为高宽度是2个更大值的距离1可以存储1的雨水下标4左边更大是2右边更大是3所以自己这行以下标4柱高1为底以min(左边更大值右边更大值)2为高宽度是2个更大值的距离3可以存储3的雨水……左边更大和右边更大有1个不存在的则存储雨水为0。 所以要用单调栈计算出上一个更大值和下一个更大值的下标leftmax和rightmax。然后i柱子处可以存储的雨水是(min(height[leftmax],height[rightmax])-height[i])*(rightmax-leftmax-1)。 怎么计算上一个更大值和下一个更大值呢还想着2次单调栈实际上1次单调栈即可。采用单调递增栈在元素 i 比栈顶大的情况下如果栈顶同时也比次栈顶要小这个时候就出现一个凹槽也就找到了上一个更大值次栈顶和下一个更大值元素i。所以这个单调递增栈必须是严格的单增这个凹槽一定是次栈顶栈顶比栈顶大的元素i。 所以如果元素i栈顶的话要么不操作要么替换这个栈顶才能满足单调栈。这里需要选择的操作是替换栈顶因为我们要求宽度的时候 如果遇到相同高度的柱子需要使用最右边的柱子来计算宽度。 如果栈顶就直接入栈。 清晰说明了3种情况 class Solution {
public:int trap(vectorint height) {int nheight.size();int count0;stackint st;st.push(0);for(int i1;in;i){if(height[i]height[st.top()]){st.pop();st.push(i);}else if(height[i]height[st.top()])st.push(i);else{while(!st.empty()height[i]height[st.top()]){//有凹槽,top是中间int midst.top();st.pop();if(!st.empty()){//取栈顶都要判断非空int hmin(height[i],height[st.top()])-height[mid];//高int wi-st.top()-1;//宽countw*h;}}st.push(i);}}return count;}
}; 相等的情况pop()之前应该检查是否为空但是初始和每一次循环结尾都有入栈操作所以这里不用加。 简化。简化后的3个pop()操作都有可能遇栈空所以都要加条件否则报错 class Solution {
public:int trap(vectorint height) {int nheight.size();int count0;stackint st;st.push(0);for(int i1;in;i){while(!st.empty()height[i]height[st.top()]){//有凹槽,top是中间int midst.top();st.pop();if(!st.empty()){//取栈顶都要判断非空int hmin(height[i],height[st.top()])-height[mid];//高int wi-st.top()-1;//宽countw*h;}}if(!st.empty()height[i]height[st.top()]){st.pop();}st.push(i);}return count;}
};
