单调栈-LeetCode 739、287（单调栈，桶计数）
单调栈-LeetCode 739、287（单调栈，桶计数）
单调栈，桶计数：LeetCode #739 287
1
编程题
【LeetCode #739】每日温度
根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
解题思路：
昨天推文中说了单调队列解决滑动窗口最大值的问题，今天来介绍一个单调栈的使用，根据题意需要找到还有多久温度会升高超过该日的天数！ 可以维护一个从栈顶到栈低依次递增的堆栈，然后遍历整个T数组，将索引号压入到堆栈中，如果当前值大于栈的栈顶对应的值，也就是T[i] > T[sta.top()], 这个时候需要删除sta.top()这个索引，并且计算索引之间的差值，即为结果！完成后将当前索引压入堆栈中。
注意：由于初始化值为0，因此如果是一个递减的温度序列，这样永远不会进入while循环，但结果却都是0，符合条件。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
stack<int> sta;
vector<int> res(T.size(), 0);
for(int i = 0; i < T.size();i++){
while(!sta.empty() && T[i] > T[sta.top()]){
res[sta.top()] = i-sta.top();
sta.pop();
}
sta.push(i);
}
return res;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/daily-temperatures
【LeetCode #287】寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1: 输入: [1,3,4,2,2] 输出: 2 示例 2:= 输入: [3,1,3,4,2] 输出: 3
解题思路：
前两种方法就不说了，从二分法开始： （二分法） 这个原理我不是太懂，但按照这个二分的样子确实可以解决这个问题，即便它不是有序的数组！ （桶计数） 由于题目是n+1个1到n的数，那么只要将对应数值放到其相应的索引号位置，如果没有在，就交换，直到遍历到的数值与其对应的数值一样，说明坑被占了，那么这个数就是答案了！ 注意：索引范围从零开始，而值得范围从1开始！
（方法一：排序法）
class Solution {
public:
int findDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
for(int i = 0; i < n-1; ++i){
if(nums[i] == nums[i+1])
return nums[i];
}
return 0;
}
};（方法二：哈希集合）
class Solution {
public:
int findDuplicate(vector<int>& nums) {
set<int> ss;
for(auto num: nums){
if(ss.count(num)){
return num;
}else{
ss.insert(num);
}
}
return 0;
}
};（方法三：二分法）
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l = 0, r = nums.size()-1;
while(l < r){
int mid = l + (r-l)/2;
int count = 0;
for(auto num: nums){
if(num <= mid){
count += 1;
}
}
if(count <= mid){
l = mid + 1;
}else{
r = mid;
}
}
return l;
}
};（方法四：桶计数法）
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size();
for(int i = 0;i < n; i++){
while(nums[i] != i+1){
if(nums[nums[i]-1] == nums[i]){
return nums[i];
}else{
swap(nums[i], nums[nums[i]-1]);
}
}
}
return 0;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-the-duplicate-number