232. 用栈实现队列 （简略）

应用栈实现队列的下列操作：

• push(x) -- 将一个元素放入队列的尾部。
• pop() -- 从队列首部移除元素。
• peek() -- 返回队列首部的元素。
• empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();queue.push(1);queue.push(2);  queue.peek();  // 返回 1queue.pop();   // 返回 1queue.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

出栈:

1. data 中除最初一个数，其余数顺次入队列 help。
2. data中惟一的一个数出队.
3. 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

1. 若 x < top, 那么 x 同时进 min 栈
2. 若 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:

输出: "([)]"输入: false

class 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)