232. 用栈实现队列（简略）
应用栈实现队列的下列操作：
- push(x) — 将一个元素放入队列的尾部。
- pop() — 从队列首部移除元素。
- peek() — 返回队列首部的元素。
- empty() — 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false阐明:
- 你只能应用规范的栈操作 — 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是非法的。
- 你所应用的语言兴许不反对栈。你能够应用 list 或者 deque（双端队列）来模仿一个栈，只有是规范的栈操作即可。
- 假如所有操作都是无效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。
解答：
用两个栈构造：push 和 pop
- 入队：进 push 栈
- 出队：
若 pop 为空，push 栈外面的数顺次倒进 pop, pop 栈顶弹出
若 pop 不为空, pop 栈顶弹出
JAVA 代码：
class MyQueue {
private Stack<Integer> push;
private Stack<Integer> pop;
/** Initialize your data structure here. */
public MyQueue() {push = new Stack<Integer>();
pop = new Stack<Integer>();}
/** Push element x to the back of queue. */
public void push(int x) {push.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {if (pop.empty()){while (!push.empty()){pop.push(push.pop());
}
}
return pop.pop();}
/** Get the front element. */
public int peek() {if (pop.empty()){while (!push.empty()){pop.push(push.pop());
}
}
return pop.peek();}
/** Returns whether the queue is empty. */
public boolean empty() {if (push.empty() && pop.empty()){return true;}
else return false;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/- 入队
工夫复杂度：O(1)
空间复杂度：O(n)
- 出队
摊还工夫复杂度：O(1)
空间复杂度：O（1）
225. 用队列实现栈（简略）
应用队列实现栈的下列操作：
- push(x) — 将元素 x 推入栈中。
- pop() — 删除栈顶的元素。
- top() — 获取栈顶元素。
- empty() — 返回栈是否为空
留神:
- 你只能应用队列的基本操作 – 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是非法的。
- 你所应用的语言兴许不反对队列。你能够应用 list 或者 deque（双端队列）来模仿一个队列 , 只有是规范的队列操作即可。
- 你能够假如所有操作都是无效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
题解：
用两个队列实现栈构造。
队列：先进先出
栈：先进后出
应用两个队列：data 和 help
出栈:
- data 中除最初一个数，其余数顺次入队列 help。
- data 中惟一的一个数出队.
- data 和 help 地址调换
入栈：间接入队列 data.
JAVA 代码：
class MyStack {
private Queue<Integer> data;
private Queue<Integer> help;
/** Initialize your data structure here. */
public MyStack() {data = new LinkedList<Integer>();
help = new LinkedList<Integer>();}
/** Push element x onto stack. */
public void push(int x) {data.add(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {while (data.size()>1){help.add(data.remove());
}
int top = data.remove();
Queue<Integer> temp = data;
data = help;
help = temp;
return top;
}
/** Get the top element. */
public int top() {while (data.size()>1){help.add(data.remove());
}
int top = data.peek();
help.add(data.remove());
Queue<Integer> temp = data;
data = help;
help = temp;
return top;
}
/** Returns whether the stack is empty. */
public boolean empty() {if (data.isEmpty()){return true;}
else return false;
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/工夫复杂度：入队 O(1), 出队 O(n)
155. 最小栈（简略）
设计一个反对 push，pop，top 操作，并能在常数工夫内检索到最小元素的栈。
- push(x) — 将元素 x 推入栈中。
- pop() — 删除栈顶的元素。
- top() — 获取栈顶元素。
- getMin() — 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.解答：
设计两个栈：data 和 min
data 代表以后栈，min 保留以后栈的最小元素。
进栈时：比拟以后元素 x 与 min 栈顶元素 top
- 若 x < top, 那么 x 同时进 min 栈
- 若 x>=top, 那么数值 top 进 min 栈
出栈时：data 和 min 同时弹出栈顶元素。
mini 的栈顶元素即为 data 栈中的最小元素。
JAVA 代码
class MinStack {
/** initialize your data structure here. */
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MinStack() {stackData = new Stack<Integer>();
stackMin = new Stack<Integer>();}
public void push(int x) {stackData.push(x);
if (!stackMin.isEmpty()) {if (x < stackMin.peek()) {stackMin.push(x);
}
else stackMin.push(stackMin.peek());
}
else{stackMin.push(x);
}
}
public void pop() {stackData.pop();
stackMin.pop();}
public int top() {return stackData.peek();
}
public int getMin() {return stackMin.peek();
}
}工夫复杂度：O(1)
空间复杂度：O(n)
20. 无效的括号 (简略)
给定一个只包含 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串，判断字符串是否无效。
无效字符串需满足：
左括号必须用雷同类型的右括号闭合。
左括号必须以正确的程序闭合。
留神空字符串可被认为是无效字符串。
示例 1:
输出: "()"
输入: true示例 2:
输出: "()[]{}"
输入: true示例 3:
输出: "(]"
输入: false示例 4:
输出: "([)]"
输入: falseclass Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();
for (int i=0; i<s.length(); i++){if (!stack.isEmpty() && ((stack.peek() == '('&& s.charAt(i)==')')||(stack.peek() == '{'&& s.charAt(i)=='}')||(stack.peek() == '['&& s.charAt(i)==']')))
stack.pop();
else stack.push(s.charAt(i));
}
return stack.isEmpty()? true: false;}
}工夫复杂度 O(n)
空间复杂度 O(n)
739. 每日温度 *（中等）
依据每日 气温 列表，请从新生成一个列表，对应地位的输入是须要再期待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该地位用 0 来代替。
例如，给定一个列表
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输入应该是 [1, 1, 4, 2, 1, 1, 0, 0]。提醒：气温 列表长度的范畴是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范畴内的整数。
题解：
1. 暴力法
每一个元素都往后找第一个比它大的数的下标
// 暴力算法
// 每一个元素都往后找比他大的数
class Solution {public int[] dailyTemperatures(int[] T) {int[] res = new int[T.length];
for(int i = 0; i<T.length; i++){for (int j = i; j<T.length; j++){if (T[j]>T[i]){res[i] = j-i;
break;
}
}
}
return res;
}
}工夫复杂度 O(n^2)
空间复杂度 O(n), 存后果
2. 用一个 next 数组存每个元素的下标 *
从后向前遍历元素，在 next 中找下标为比以后元素大的元素，next 中值最小的元素即为离以后元素最近的比它的元素。
class Solution {public int[] dailyTemperatures(int[] T) {int[] next = new int[101];
Arrays.fill(next, Integer.MAX_VALUE);
int[] res = new int[T.length];
for (int i=T.length-1; i>=0; i--){int curr = Integer.MAX_VALUE; // 在 next 中以后元素值, 即比 T[i]大的元素的下标
// 在 next 数组中找比以后元素大且离以后元素最近的元素，失去其下标
for (int j = T[i]+1; j<101; j++){if (next[j] < curr){curr = next[j];
}
}
if (curr<Integer.MAX_VALUE)
res[i] = curr-i;
next[T[i]] = i;
}
return res;
}
}工夫复杂度 O(nw), w 为元素取值的范畴宽度
空间复杂度 O(n+w)
3. 利用栈 *
栈中寄存元素下标。
倒序遍历数组，若以后元素比栈中下标对应元素大，出栈，直到以后元素小于栈中小标对应的元素。那么栈中就是须要找到的下标。
// 栈
class Solution {public int[] dailyTemperatures(int[] T) {int[] res = new int[T.length];
Stack<Integer> stack = new Stack<>();
for (int i = T.length-1; i>=0; i--){while (!stack.isEmpty() && T[i]>=T[stack.peek()]){stack.pop();
}
if (!stack.isEmpty())
res[i] = stack.peek()-i;
stack.push(i);
}
return res;
}
}工夫复杂度 O(n)
空间复杂度 O(n)
503. 下一个更大元素 II
给定一个循环数组（最初一个元素的下一个元素是数组的第一个元素），输入每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历程序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜寻它的下一个更大的数。如果不存在，则输入 -1。
示例 1:
输出: [1,2,1]
输入: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数须要循环搜寻，后果也是 2。留神: 输出数组的长度不会超过 10000。
题解：利用栈
与 739 题相似，不同的是这题给出的数组为循环数组。
对循环数组的拜访可用以下模式：i % nums.length, i为任意数字。
而对于这题，咱们只须要反复拜访数组两次，所以 i 的取值为 0~2*nums.length-1
能够了解为数组中的每一个数字，心愿能拜访到它前面的数字，也能拜访到它后面的数字。
class Solution {public int[] nextGreaterElements(int[] nums) {
int size = nums.length;
int[] res = new int[size];
Stack<Integer> stack = new Stack<>();
for (int i = 2*size-1; i>=0; i--){while (!stack.isEmpty() && nums[i%size] >= nums[stack.peek()]){stack.pop();
}
res[i%size] = stack.isEmpty()? -1: nums[stack.peek()];
stack.push(i%size);
}
return res;
}
}工夫复杂度 O(n)
空间复杂度 O(n)