一、前言
参考文献:代码随想录;
终于结束了动态规划了,今天的主题就是单调栈;
单调栈的作用就是将你之前遍历过的数组以单调的形式存到栈中,方便对数据进行判断;
二、每日温度
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.
我们都是岛屿,在误解的海洋中彼此撒着谎。