More content:LeetCode hot100@栈
96. 下一个更大元素 I✅
单调栈 + 哈希
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> sk; // 单调栈存下标,保持对应元素值递减
unordered_map<int, int> mp;
for(int i = 0; i < nums2.size(); i++) {
while(!sk.empty() && nums2[i] > nums2[sk.top()]) {
mp[nums2[sk.top()]] = nums2[i];
sk.pop();
}
sk.push(i);
}
vector<int> res(nums1.size(), -1);
for(int i = 0; i < nums1.size(); i++) {
if(mp.find(nums1[i]) != mp.end()) {
res[i] = mp[nums1[i]];
}
}
return res;
}
};
496. 下一个更大元素 I✅
在上一题的基础上 先扩充一倍 因为总能在两次遍历内找到 最后再将结果缩减一倍
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int> sk; // 单调栈存下标,保持对应元素值递减
vector<int> res(2 * nums.size(), -1);
vector<int> v(nums);
v.insert(v.end(), nums.begin(), nums.end()); // 拼接数组
for(int i = 0; i < v.size(); i++) {
while(!sk.empty() && v[i] > v[sk.top()]) {
res[sk.top()] = v[i];
sk.pop();
}
sk.push(i);
}
res.resize(nums.size());
return res;
}
};
402. 移掉 K 位数字❌
比较两个数字的大小,是从最高位开始比较的,因此尽量使最高位变小,也就是改造使得数字从高位到低位递增。
因此想到维护一个递增单调栈来保证最高位最小,当遇到小于栈顶的元素时,就把栈顶这个大数去掉。
class Solution {
public:
string removeKdigits(string num, int k) {
stack<int> sk; // 递增栈 存下标 以此来保证最高位最小
for(int i = 0; i < num.size(); i++) {
while(!sk.empty() && num[i] < num[sk.top()] && k > 0) {
sk.pop();
k--;
}
sk.push(i);
}
while(!sk.empty() && k > 0) { // 如果 k 还有余量
sk.pop();
k--;
}
// cout << "---------------------" << endl;
// stack<int> tmp = sk;
// while(!tmp.empty()) {
// cout << tmp.top() << " ";
// tmp.pop();
// }
// cout << endl << "---------------------" << endl;
if(sk.empty()) return "0";
string res;
while(!sk.empty()) {
res += num[sk.top()];
sk.pop();
}
reverse(res.begin(), res.end());
// 处理前导零
int p = 0;
int i = 0;
for(i = 0; i < res.size(); i++) {
if(res[i] == '0') p++;
else break;
}
if(i == res.size()) return "0"; // 只有零的情况
return res.substr(i); // 只填第一个参数
}
};
42. 接雨水❌
Solution1:双指针 (按列计算)
每一列雨水的高度取决于,该列左侧最高的柱子和右侧最高的柱子中较矮的那个柱子的高度 – 自身高度
Solution2:单调栈 (按行计算)
栈底到栈头元素递减,因为一旦要添加的柱子高度大于栈头元素,说明出现凹槽了
此时,栈头元素就是凹槽底部的柱子,栈头第二个元素就是凹槽左边的柱子,而添加的元素就是凹槽右边的柱子
class Solution1 {
public:
int trap(vector<int>& height) {
int res = 0;
int len = height.size();
//记录当前列的左右两边的最高列
vector<int> lmax(len);
vector<int> rmax(len);
lmax[0] = height[0];
for(int i = 1; i < len; i++) {
lmax[i] = max(lmax[i-1], height[i]);
}
rmax[len - 1] = height[len - 1];
for(int i = len - 2; i >= 0; i--) {
rmax[i] = max(rmax[i+1], height[i]);
}
for(int i = 0; i < height.size(); i++) {
int x = min(lmax[i], rmax[i]) - height[i]; //第一列和最后一列的x算出来是0
if(x > 0) res += x; //是正数才说明能接住雨水,负数的情况比如最高列
}
return res;
}
};
class Solution2 {
public:
int trap(vector<int>& height) {
stack<int> sk; //存下标
int res = 0;
sk.push(0);
for(int i = 1; i < height.size(); i++) {
while(!sk.empty() && height[i] > height[sk.top()]) { //出现凹槽
int mid = height[sk.top()]; //凹槽中间柱子高度
sk.pop();
if(!sk.empty()) {
int left = height[sk.top()]; //凹槽左边柱子高度
int right = height[i]; //凹槽右边柱子高度
int h = min(left, right) - mid;
int w = i - sk.top() - 1;
res += h * w; //高×宽
}
}
sk.push(i);
}
return res;
}
};