共计 2802 个字符，预计需要花费 8 分钟才能阅读完成。
读完本文，你能够去力扣拿下如下题目：
496. 下一个更大元素 I
503. 下一个更大元素 II
1118. 一月有多少天
———–
栈（stack）是很简略的一种数据结构，先进后出的逻辑程序，合乎某些问题的特点，比如说函数调用栈。
枯燥栈实际上就是栈，只是利用了一些奇妙的逻辑，使得每次新元素入栈后，栈内的元素都放弃有序（枯燥递增或枯燥递加）。
听起来有点像堆（heap）？不是的，枯燥栈用处不太宽泛，只解决一种典型的问题，叫做 Next Greater Element。本文用解说枯燥队列的算法模版解决这类问题，并且探讨解决「循环数组」的策略。
首先，解说 Next Greater Number 的原始问题：给你一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。不好用语言解释分明，间接上一个例子：
给你一个数组 [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。
解释：第一个 2 前面比 2 大的数是 4; 1 前面比 1 大的数是 2；第二个 2 前面比 2 大的数是 4; 4 前面没有比 4 大的数，填 -1；3 前面没有比 3 大的数，填 -1。
这道题的暴力解法很好想到，就是对每个元素前面都进行扫描，找到第一个更大的元素就行了。然而暴力解法的工夫复杂度是 O(n^2)。
这个问题能够这样形象思考：把数组的元素设想成并列站立的人，元素大小设想成人的身高。这些人面对你站成一列，如何求元素「2」的 Next Greater Number 呢？很简略，如果可能看到元素「2」，那么他前面可见的第一个人就是「2」的 Next Greater Number，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。
这个情景很好了解吧？带着这个形象的情景，先来看下代码。
vector<int> nextGreaterElement(vector<int>& nums) {vector<int> ans(nums.size()); // 寄存答案的数组
stack<int> s;
for (int i = nums.size() - 1; i >= 0; i--) { // 倒着往栈里放
while (!s.empty() && s.top() <= nums[i]) { // 断定个子高矮
s.pop(); // 矮个起开，反正也被挡着了。。。}
ans[i] = s.empty() ? -1 : s.top(); // 这个元素身后的第一个高个
s.push(nums[i]); // 进队，承受之后的身高断定吧！}
return ans;
}这就是枯燥队列解决问题的模板。for 循环要从后往前扫描元素，因为咱们借助的是栈的构造，倒着入栈，其实是正着出栈。while 循环是把两个“高个”元素之间的元素排除，因为他们的存在没有意义，后面挡着个“更高”的元素，所以他们不可能被作为后续进来的元素的 Next Great Number 了。
这个算法的工夫复杂度不是那么直观，如果你看到 for 循环嵌套 while 循环，可能认为这个算法的复杂度也是 O(n^2)，然而实际上这个算法的复杂度只有 O(n)。
剖析它的工夫复杂度，要从整体来看：总共有 n 个元素，每个元素都被 push 入栈了一次，而最多会被 pop 一次，没有任何冗余操作。所以总的计算规模是和元素规模 n 成正比的，也就是 O(n) 的复杂度。
当初，你曾经把握了枯燥栈的应用技巧，来一个简略的变形来加深一下了解。
给你一个数组 T = [73, 74, 75, 71, 69, 72, 76, 73]，这个数组寄存的是近几天的天气气温（这气温是铁板烧？不是的，这里用的华氏度）。你返回一个数组，计算：对于每一天，你还要至多等多少天能力等到一个更温暖的气温；如果等不到那一天，填 0。
举例：给你 T = [73, 74, 75, 71, 69, 72, 76, 73]，你返回 [1, 1, 4, 2, 1, 1, 0, 0]。
解释：第一天 73 华氏度，第二天 74 华氏度，比 73 大，所以对于第一天，只有等一天就能等到一个更温暖的气温。前面的同理。
你曾经对 Next Greater Number 类型问题有些敏感了，这个问题实质上也是找 Next Greater Number，只不过当初不是问你 Next Greater Number 是多少，而是问你以后间隔 Next Greater Number 的间隔而已。
雷同类型的问题，雷同的思路，间接调用枯燥栈的算法模板，稍作改变就能够啦，间接上代码把。
vector<int> dailyTemperatures(vector<int>& T) {vector<int> ans(T.size());
stack<int> s; // 这里放元素索引，而不是元素
for (int i = T.size() - 1; i >= 0; i--) {while (!s.empty() && T[s.top()] <= T[i]) {s.pop();
}
ans[i] = s.empty() ? 0 : (s.top() - i); // 失去索引间距
s.push(i); // 退出索引，而不是元素
}
return ans;
}枯燥栈解说结束。上面开始另一个重点：如何解决「循环数组」。
同样是 Next Greater Number，当初假如给你的数组是个环形的，如何解决？
给你一个数组 [2,1,2,4,3]，你返回数组 [4,2,4,-1,4]。领有了环形属性，最初一个元素 3 绕了一圈后找到了比本人大的元素 4。
首先，计算机的内存都是线性的，没有真正意义上的环形数组，然而咱们能够模拟出环形数组的成果，个别是通过 % 运算符求模（余数），取得环形特效：
int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {print(arr[index % n]);
index++;
}回到 Next Greater Number 的问题，减少了环形属性后，问题的难点在于：这个 Next 的意义不仅仅是以后元素的左边了，有可能呈现在以后元素的右边（如上例）。
明确问题，问题就曾经解决了一半了。咱们能够思考这样的思路：将原始数组“翻倍”，就是在前面再接一个原始数组，这样的话，依照之前“比身高”的流程，每个元素不仅能够比拟本人左边的元素，而且也能够和右边的元素比拟了。
怎么实现呢？你当然能够把这个双倍长度的数组结构进去，而后套用算法模板。然而，咱们能够不必结构新数组，而是利用循环数组的技巧来模仿。间接看代码吧：
vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();
vector<int> res(n); // 寄存后果
stack<int> s;
// 伪装这个数组长度翻倍了
for (int i = 2 * n - 1; i >= 0; i--) {while (!s.empty() && s.top() <= nums[i % n])
s.pop();
res[i % n] = s.empty() ? -1 : s.top();
s.push(nums[i % n]);
}
return res;
}
