一、前言
参考文献：代码随想录；
终于结束了动态规划了，今天的主题就是单调栈；
单调栈的作用就是将你之前遍历过的数组以单调的形式存到栈中，方便对数据进行判断；
二、每日温度
1、思路：
（1）首先是暴力思路：
两层for循环，一层遍历当前位置的距离高温的距离，第二层就是找高温；
代码逻辑如下：
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
if (temperatures.size() == 1) return temperatures;
int n = temperatures.size();
vector<int> answer(n, 0);
for (int i = 0; i < n - 1; i++) {
int dif = 0;
int max = temperatures[i];
for (int j = i + 1; j < n; j++) {
if (temperatures[i] < temperatures[j] && max < temperatures[j]) {
// max = temperatures[j];
answer[i] = j - i;
break;
}
}
}
return answer;
}
};（此方法超时）
（2）接下来是单调栈的思路：
首先需要定义一个栈，确定他是升序还是降序，在这里我们发现我们需要比较的是比当前温度大的位置，所以我们需要去升序排列；
而且还要确定存入的是什么，我们需要求的是距离的天数，所以存下标；
其次是添加逻辑，分为两种情况，一种相等，一种小于当前温度，那就添加，；
当不是时，就需要不断地往下找，找到为止（while循环）；
2、整体代码如下：
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> st;
vector<int> answer(temperatures.size(), 0);
st.push(0);
for (int i = 1; i < temperatures.size(); i++) {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
answer[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
return answer;
}
};三、下一个更大元素
1、思路：
（1）首先展示的还是暴力：
就是三重循环，一层一层的套，第一层确定目标值，第二层找目标值，第三层找，目标大的值；
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> st;
vector<int> answer(nums1.size(), -1);
for (int i = 0; i < nums1.size(); i++) {
for (int j = 0; j < nums2.size(); j++) {
if (nums1[i] == nums2[j]) {
for (int k = j + 1; k < nums2.size(); k++) {
if (nums2[j] < nums2[k]) {
answer[i] = nums2[k];
break;
}
}
}
}
}
return answer;
}
};（这个可以AC）
（1） 单调栈思路：
首先需要map哈希表来存储nums1的值和下标的键值对，方便在寻找nums2时迅速匹配到nums1中的值是否存在；
然后还是使用stack存储nums2中的下标，升序排列，还是寻找的是比当前元素大的值；
一共分为三种情况；
2、整体代码如下：
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> st;
vector<int> answer(nums1.size(), -1);
unordered_map<int, int> my_map;
for (int i = 0; i < nums1.size(); i++) {
my_map[nums1[i]] = i;
}
// 存入第一个元素的下标（nums2）
st.push(0);
for (int i = 1; i < nums2.size(); i++) {
if (nums2[i] < nums2[st.top()]) {
st.push(i);
} else if (nums2[i] == nums2[st.top()]) {
st.push(i);
} else {
while (!st.empty() && nums2[i] > nums2[st.top()]) {
if (my_map.count(nums2[st.top()]) > 0) {
int idx = my_map[nums2[st.top()]];
answer[idx] = nums2[i];
}
st.pop();
}
// 别忘记了把i加进去
st.push(i);
}
}
return answer;
}
};Study time 1h;
Leave message:
We're all islands shouting lies to each other across seas of misunderstanding.
我们都是岛屿，在误解的海洋中彼此撒着谎。