寻找手机网站建设,网站建设要注意,网站地图模板下载,一站式网络推广服务LeetCode 503- 下一个更大元素 II
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
题目描述#xff1a;给定一个循环数组 nums #xff08; nums[nums.length - 1] 的下一个元素是 nums[0] #xff09;#xff0c;返回 num…LeetCode 503- 下一个更大元素 II
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给定一个循环数组 nums nums[nums.length - 1] 的下一个元素是 nums[0] 返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出 -1 。
解题思路
本题也是单调栈的一个应用和温度那题一模一样就是多了一个循环数组成环了该怎么处理首先就想到把给定的数组和自己拼接起来当做新的数组再用单调栈操作即可但这样会导致很多冗余的操作。所以想到取余来算模拟拼接了数组的情况。
// 版本二
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {vectorint result(nums.size(), -1);if (nums.size() 0) return result;stackint st;for (int i 0; i nums.size() * 2; i) {// 模拟遍历两边nums注意一下都是用i % nums.size()来操作while (!st.empty() nums[i % nums.size()] nums[st.top()]) {result[st.top()] nums[i % nums.size()];st.pop();}st.push(i % nums.size());}return result;}
};
总结
单调栈加环形数组的应用。
LeetCode 42- 接雨水
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
解题思路
用单调栈来解题递增的单调栈由于栈顶每次都是最小的元素我们接雨水其实就是找中间元素的左边第一个比他高的元素和右边第一个比他高的元素。右边第一个比他高的元素我们可以在入栈之前判断而左边第一个比他高的元素就是他在栈中的下面的一个元素。 class Solution {
public:int trap(vectorint height) {if (height.size() 2) return 0; // 可以不加stackint st; // 存着下标计算的时候用下标对应的柱子高度st.push(0);int sum 0;for (int i 1; i height.size(); i) {if (height[i] height[st.top()]) { // 情况一st.push(i);} if (height[i] height[st.top()]) { // 情况二st.pop(); // 其实这一句可以不加效果是一样的但处理相同的情况的思路却变了。st.push(i);} else { // 情况三while (!st.empty() height[i] height[st.top()]) { // 注意这里是whileint mid st.top();st.pop();if (!st.empty()) {int h min(height[st.top()], height[i]) - height[mid];int w i - st.top() - 1; // 注意减一只求中间宽度sum h * w;}}st.push(i);}}return sum;}
};
总结
单调栈的应用需要多想想为什么这里能用到单调栈。
