关于算法:leetcode-栈和队列

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

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）

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

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)

设计一个反对 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)

给定一个只包含 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串，判断字符串是否无效。
无效字符串需满足：
左括号必须用雷同类型的右括号闭合。
左括号必须以正确的程序闭合。
留神空字符串可被认为是无效字符串。

示例 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)

依据每日气温列表，请从新生成一个列表，对应地位的输入是须要再期待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该地位用 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)

给定一个循环数组（最初一个元素的下一个元素是数组的第一个元素），输入每个元素的下一个更大元素。数字 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)

关于算法:leetcode-栈和队列

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

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

155. 最小栈（简略）

20. 无效的括号 (简略)

739. 每日温度 *（中等）

503. 下一个更大元素 II

Just My Socks（注册教程内含优惠码）

关于算法:leetcode-栈和队列

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

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

155. 最小栈（简略）

20. 无效的括号 (简略)

739. 每日温度 *（中等）

503. 下一个更大元素 II

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）