题目
232.用栈实现队列
class MyQueue {
private Stack<Integer> in = new Stack<>();
private Stack<Integer> out = new Stack<>();
public void push(int x) {
in.push(x);
}
public int pop() {
in2out();
return out.pop();
}
public int peek() {
in2out();
return out.peek();
}
private void in2out() {
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}225.用队列实现栈
class MyStack {
private Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
queue.add(x);
int cnt = queue.size();
while (cnt-- > 1) {
queue.add(queue.poll());
}
}
public int pop() {
return queue.remove();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}155.最小栈
class MinStack {
private Stack<Integer> dataStack;
private Stack<Integer> minStack;
private int min;
public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
min = Integer.MAX_VALUE;
}
public void push(int x) {
dataStack.add(x);
min = Math.min(min, x);
minStack.add(min);
}
public void pop() {
dataStack.pop();
minStack.pop();
min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peek();
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}20.有效地括号
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char cStack = stack.pop();
boolean b1 = c == ')' && cStack != '(';
boolean b2 = c == ']' && cStack != '[';
boolean b3 = c == '}' && cStack != '{';
if (b1 || b2 || b3) {
return false;
}
}
}
return stack.isEmpty();
}
}739.每日温度
求数组中元素与下一个比它大元素之间的距离
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] dist = new int[n];
Stack<Integer> indexs = new Stack<>();
for (int curIndex = 0; curIndex < n; curIndex++) {
while (!indexs.isEmpty() && temperatures[curIndex] > temperatures[indexs.peek()]) {
int preIndex = indexs.pop();
dist[preIndex] = curIndex - preIndex;
}
indexs.add(curIndex);
}
return dist;
}
}503.下一个更大的元素II
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] next = new int[n];
Arrays.fill(next, -1);
Stack<Integer> pre = new Stack<>();
for (int i = 0; i < n * 2; i++) {
int num = nums[i % n];
while (!pre.isEmpty() && nums[pre.peek()] < num) {
next[pre.pop()] = num;
}
if (i < n){
pre.push(i);
}
}
return next;
}
}