496. 下一个更大元素Ⅰ
题目
题意
给我们一个数组，找这个数组里面每个数在另外一个数组里位置右边更大一点点的数
就像排队一样：
如果 num1 = [3, 2, 4, 1]
num2 = [3, 2, 1]
|| || | || | | |
思路
可以使用单调栈来解决这个问题
单调栈的特点是，压栈时候一定会按照某个顺序（升序或降序），如果有一个元素压入后打破了这个顺序，就要不断把当前的栈顶元素弹出，直到压入这个元素符合顺序
这么一看：
- 当我可以正常压栈的时候，说明下一个人没有我高（下一个数比我小），我可以继续压
- 当我不能压栈的时候，这时候我弹出的数是n，n的下一个比我高的数，就是我现在想压入的数
所以可以通过使用单调栈，来模拟这个循环下一个比我高的人的过程。然后用一个hashmap， 来保存每一个数更大一点点的数。
push 3 success ---> stack:3 map:push 2 success ---> stack:3 2 map:push 4 failed ---> stack:3 map:(2, 4)push 4 failed ---> stack: map:(2, 4), (3, 4)push 4 success ---> stack:4 map:(2, 4), (3, 4)push 1 success ---> stack:4 1 map:(2, 4), (3, 4)剩下的说明木有找到pop 1 success ---> stack:4 map:(2, 4), (3, 4), (1, -1)pop 4 success ---> stack: map:(2, 4), (3, 4), (1, -1), (4, -1)
单调栈模板
以用单调栈处理 nums, 栈底最大 为例子
stack<int> st;
for(int num : nums){
while(!st.empty() && num > st.top()) { // 如果大于栈顶元素，就不断弹出
int out = st.top();
st.pop();
// 处理弹出的数......
}
st.push(num);
}
最终代码
用一个哈希表，在数组弹出的时候，以弹出的数为key， 想要尝试压入的数为value
存到哈希表当中。
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int>s;//临时栈
unordered_map<int,int>num_map; //哈希表
int size = nums1.size();
vector<int>vec_num;//存储下一个最大值的vector
for(int i = 0;i < nums2.size();++i){
while(!s.empty() && nums2[i]>s.top()){
num_map[s.top()] = nums2[i];
s.pop();
}
s.push(nums2[i]);
}
while(!s.empty()){
num_map[s.top()] = -1;
s.pop();
}
for(int i = 0;i<size;++i)
vec_num.push_back(num_map[nums1[i]]);
return vec_num;
}
};
155. 最小栈
题目
题意
基于栈实现一个栈，这个栈附带一个获取当前栈最小值的功能
思路
使用2个栈， 一个栈用来当正常的栈用，另外一个辅助栈保存在当前情况下，的最小值。
因为每次压栈都会比较一次，所以辅助栈的栈顶一定是当前最小的
push 3 ----> st:3 min_st:3
push 9 ----> st:3 9 min_st:3 3
push 1 ----> st:3 min_st:3 3 1
代码实现
#include <stack>
class MinStack {
public:
stack<int> st;
stack<int> min_st;
/** initialize your data structure here. */
MinStack() {
min_st.push(INT_MAX); // 先压入一个最大值，这样可以不用每次在压入最小栈时，判断是否为空
}
void push(int x) {
st.push(x);
min_st.push( min(x, min_st.top()) ); //比较当前数和辅助栈栈顶谁比较小
}
void pop() {
st.pop();
min_st.pop();
}
int top() {
return st.top();
}
int getMin() {
return min_st.top();
}
};
225. 用队列实现栈
题目
题意
用queue（先进先出）实现stack（后进后出）
思路
1. 使用两个队列
队列的特性是先进先出。对于栈来说，想pop的元素在队头。
因此可以把队头后面的所有元素，推到另外一个队列里面
queue1: 1 2 3 4 queue2 : =====> stack 4 3 2 1
push 9:
queue1: 9 1 2 3 4 queue2 : =====> stack 9 4 3 2 1
pop
queue1: 9 queue2 : 1 2 3 4
return 9 ,queue1 = queue2, queue2.clear
queue1: 1 2 3 4 queue2 : =====> stack 4 3 2 1
2. 使用一个队列
可以直接把弹出的元素加到队列尾部，就不用另外一个栈来保存
queue1: 1 2 3 4 queue2 : =====> stack 4 3 2 1
push 9:
queue1: 9 1 2 3 4 queue2 : =====> stack 9 4 3 2 1
pop
queue1: 1 2 3 4 9(pop) queue2 : =====> stack 4 3 2 1
实现代码
两个队列
class MyStack {
public:
queue<int> que1;
queue<int> que2; // 辅助队列
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
que1.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int size = que1.size();
size--;
while (size--) { // 将que1 导入que2，但要留下最后一个元素
que2.push(que1.front());
que1.pop();
}
int result = que1.front(); // 留下的最后一个元素就是我们要返回的值
que1.pop();
que1 = que2; // 再将que2赋值给que1
while(!que2.empty()) { // 清空que2
que2.pop();
}
return result;
}
/** Get the top element. */
int top() {
return que1.back();
}
/** Returns whether the stack is empty. */
bool empty() {
return que1.empty();
}
};
一个队列
class MyStack {
public:
queue<int> que;
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
que.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int size = que.size();
size--;
while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
que.push(que.front());
que.pop();
}
int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
que.pop();
return result;
}
/** Get the top element. */
int top() {
return que.back();
}
/** Returns whether the stack is empty. */
bool empty() {
return que.empty();
}
};
剑指 Offer 58 - II. 左旋转字符串
题目
题意
思路
实现
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder res = new StringBuilder();
for(int i = n; i < s.length(); i++)
res.append(s.charAt(i));
for(int i = 0; i < n; i++)
res.append(s.charAt(i));
return res.toString();
}
}
若有收获，就点个赞吧
0 人点赞
