- 栈相关
- 堆相关
1. 栈相关
1.1 题目类型以及做题小方法
主要有两类，一类与数据结构相关，一类与单调栈相关
建立在栈的数据结构类型的题目，一种是要求有效的字符串，例如左右括号进行匹配，这里的做题小套路是遇到右括号就对栈中元素进行抵消或求算一波； 另一种是验证栈序列，或者用栈的特点生成最小栈或者队列一类的。
-
单调栈是比较特殊的栈结构，分为单调递增栈和单调递减栈，即从栈底元素到栈顶元素呈单调递增或单调递减，栈内序列满足单调性的栈；
以单调递增栈为例，实现方式为：- 如果新的元素比栈顶元素小，则出栈，直至栈顶元素小于新的元素
- 如果新的元素比栈顶元素大，则入栈
以该方式形成的栈，栈内会是递增的，且当元素出栈的时候，说明要加入的元素是该元素向后找到的第一个比它小的元素
单调栈用来解决下一个更大(更小)的元素相关问题，可以在O(n)时间内解决
1.2 Leetcode实例
q20 有效的括号
HashMap<Character, Character> validParentheses;
public void registerValidParentheses(){
validParentheses = new HashMap<>();
validParentheses.put(')','(');
validParentheses.put('}','{');
validParentheses.put(']','[');
}
/**
* 使用栈的思路
* 栈的特点在于如果字符串具有固定的规律的话，
* 遍历到每一个闭合处的字符，栈顶的元素就是要进行比对位置的元素
*
* 栈中元素的特征是都是左括号从左往右放置到栈中，有合适的右括号过来的话，
* 就将指定的左括号进行消除或者返回false
*
* 所以整个做题思路是:
* 1. 遍历字符串，如果是右闭合字符，就让栈顶元素出栈，判断栈顶元素是否和和当前字符是一对，不是返回false，是的话继续遍历
* 如果是左开字符，就把元素放入到栈之中
* 2. 最后返回stack是否为空判断这个字符串是都是valid的
*
* @param s
* @return
*/
public boolean isValidTwo(String s) {
registerValidParentheses();
Stack<Character> stack = new Stack<>();
for (int i=0;i<s.length();i++){
char current = s.charAt(i);
if (validParentheses.containsKey(current)){
char top = stack.isEmpty()?'#':stack.pop();
if (top != validParentheses.get(current)){
return false;
}
} else {
stack.push(current);
}
}
return stack.isEmpty();
}
q32 最长有效括号
/**
* 使用栈，因为还是类似匹配的过程，栈中就需要是可以累积左括号的index的，
* 然后每个右括号一过来就可以带走一个栈顶元素，
* 带走的大概率是左括号，若带走的若是左括号，那这个左括号则是和他成对的左括号
*
* 但是不可避免栈中没有左括号的存货，
* 因此，若栈顶出栈栈为空就把当前元素的index放进去 -- 标杆记录不能形成有效括号的位置
*
* @param s
* @return
*/
public int longestValidParenthesesTwo(String s) {
int res = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i=0;i<s.length();i++){
if (s.charAt(i)=='('){
stack.push(i);
}else {
stack.pop();
if (stack.isEmpty()){
stack.push(i);
}else {
res = Math.max(res, i-stack.peek());
}
}
}
return res;
}
q155 最小栈
/**
* 这道题与栈的特征相关
* 我这里是使用链表的方式实现Stack
*
* 栈是后进先出的特征，所以把新生成的元素放到链表的头部，这样删除起来也方便
* Min栈要知道当前链表的最小值，所以就在每个栈节点增加一个值来计算截止到当前位置的链表的最小值
*/
private Node top;
class Node{
private int data;
private int min;
private Node next;
public Node(int data){
this.data = data;
}
}
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
Node newNode = new Node(x);
newNode.next = top;
int min = top == null?x:Math.min(x,top.min);
newNode.min = min;
top = newNode;
}
public void pop() {
top = top.next;
}
public int top() {
return top.data;
}
public int getMin() {
return top.min;
}
q224 基本计算器
/**
* 这个使用栈是
* 1.为了记录括号出现，要及时计算括号之中元素的和
* 2.记录数字和符号
*
* 我们要把数据和符号都存入到栈中，因为栈是后进先出，所以正着直接放会让符号和数字对出错
* 使用字符串反向读取然后把数字和符号放入到栈中，然后正常出栈进行计算
*
* @param s
* @return
*/
public int calculateTwo(String s){
Stack<Object> stack = new Stack<>();
int n = 0, currNum = 0;
for (int i=s.length()-1;i>=0;i--){
if (Character.isDigit(s.charAt(i))){
currNum += (s.charAt(i)-'0')*Math.pow(10,n);
n++;
} else if (s.charAt(i) != ' '){
if (n>0){
stack.push(currNum);
n=0;
currNum = 0;
}
if (s.charAt(i) == '('){
int tempRes = evaluateExprTwo(stack);
stack.pop();
stack.push(tempRes);
} else {
//这时候放的是'+' '-' 或者 ')'
stack.push(s.charAt(i));
}
}
}
//遍历到最后的时候，若还有数字要把数字加到栈之中
if (n!=0){
stack.push(currNum);
}
return evaluateExprTwo(stack);
}
public int evaluateExprTwo(Stack<Object> stack){
int res = 0;
if (!stack.empty()){
res = (int) stack.pop();
}
while (!stack.isEmpty()&& (char)stack.peek() != ')'){
char sign = (char) stack.pop();
if (sign == '+'){
res += (int) stack.pop();
} else {
res -= (int) stack.pop();
}
}
return res;
}
q232 用栈实现队列
/**
* 使用两个栈，一个作为中间过渡栈，另一个是成为队列的栈
*
* stackQue之中存储的永远都是已经排列好的倒序的栈的元素
* font中存储的最开始的队头元素，在最开始放进去元素的时候会更新font元素以及pop出来元素之后更新font元素
* temp的作用是为了添加元素的时候 作为中间栈先把元素倒置过来放进去新元素，之后再把temp的元素放回到stackQue之中
*/
private int front;
private Stack<Integer> stackQue = new Stack<>();
private Stack<Integer> temp = new Stack<>();
/** Initialize your data structure here. */
public MyQueue() {
}
/** Push element x to the back of queue.
*
* Time Complexity: O(n)
* Space Complexity: O(n)
**/
public void push(int x) {
if (stackQue.isEmpty()){
front = x;
}
while (!stackQue.isEmpty()){
temp.push(stackQue.pop());
}
temp.push(x);
while (!temp.isEmpty()){
stackQue.push(temp.pop());
}
}
/** Removes the element from in front of queue and returns that element.
*
* Time complexity : O(1).
* Space complexity : O(1).
**/
public int pop() {
int res =stackQue.pop();
if (!stackQue.isEmpty()){
front = stackQue.peek();
}
return res;
}
/** Get the front element. 获取的是最开始的队头元素
*
* Time complexity : O(1).
* Space complexity : O(1).
**/
public int peek() {
return front;
}
/** Returns whether the queue is empty.
*
* Time complexity : O(1).
* Space complexity : O(1).
**/
public boolean empty() {
return stackQue.isEmpty();
}
public static void main(String[] args) {
MyQueue myQueue = new MyQueue();
myQueue.push(1);
myQueue.push(2);
System.out.println(myQueue.peek());
}
q316 去除重复字母
/**
* 使用栈，这道题本质上是想形成单调递增栈，但是在形成单调递增栈的时候有一些限制条件
* 1. 要看当前栈顶元素在后面还会不会出现，如果不会出现的话栈之中的元素是不能出栈的
*
* 去重的方式是看栈之中有没有当前要访问的元素，如果有的话就跳过这次循环
* @param s
* @return
*/
public String removeDuplicateLettersTwo(String s){
if (s==null || s.length() == 0)
return s;
int[] lastSeenIndexs = lastSeenCharacter(s);
//使用useOrNot去重
boolean[] usedOrNot = new boolean[26];
//stack中存储的是index
Deque<Integer> deque = new ArrayDeque<>();
for (int i=0;i<s.length();i++){
char currChar = s.charAt(i);
if (usedOrNot[currChar-'a']) continue;
usedOrNot[currChar-'a'] = true;
//使用单调栈来解题
while (!deque.isEmpty() && (s.charAt(deque.peek())>currChar && lastSeenIndexs[s.charAt(deque.peek())-'a']>i))
{
usedOrNot[s.charAt(deque.pop())-'a'] = false;
}
deque.push(i);
}
return toString(deque,s);
}
private int[] lastSeenCharacter(String s){
int[] lastSeen = new int[26];
for (int i=0;i<s.length();i++){
lastSeen[s.charAt(i)-'a'] = i;
}
return lastSeen;
}
private String toString(Deque<Integer> stack, String text) {
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty())
sb.append(text.charAt(stack.removeLast()));
return sb.toString();
}
q84 柱状图中最大的矩阵
/**
* 所形成的矩阵的面积的求算方式是：
* 要找到每个高度左侧比它低的位置以及右侧比它低的地方，然后可以确定矩阵的宽度
* 1. 关键点要找左侧和右侧比自己低的点，所以可以使用单调递增栈
* 当栈顶需要出栈的时候该高度的面积就是可以计算的了
* @param heights
* @return
*/
public int largestRectangleArea(int[] heights) {
int res = 0;
Stack<Integer> stack = new Stack<>();
int[] new_heights = new int[heights.length+2];
System.arraycopy(heights, 0, new_heights, 1, heights.length);
for (int i=0;i<new_heights.length;i++){
while (!stack.isEmpty() && new_heights[stack.peek()]>new_heights[i]){
int curHeight = new_heights[stack.pop()];
res = Math.max(res, (i-stack.peek()-1)*curHeight);
}
stack.push(i);
}
return res;
}
q496 下一个最大元素
/**
* 就是要记录nums2数组之中下一个比自己大的元素
* 这个时候可以使用单调递减栈
* 1. 当栈顶元素需要出栈的时候说明找到了下一个比自己大的元素
* 2. 如果最后栈中还有元素，那么他们都没有比自己大的元素，对应值为-1
* @param nums1
* @param nums2
* @return
*/
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] res = new int[nums1.length];
HashMap<Integer, Integer> kv = new HashMap<>();
Stack<Integer> decrease = new Stack<>();
if (nums2.length==0) return res;
decrease.push(nums2[0]);
for (int i=1;i<nums2.length;i++){
while (!decrease.isEmpty()&& decrease.peek() < nums2[i]){
kv.put(decrease.pop(),nums2[i]);
}
decrease.push(nums2[i]);
}
while (!decrease.isEmpty()){
kv.put(decrease.pop(),-1);
}
for (int i=0;i<nums1.length;i++){
res[i] = kv.get(nums1[i]);
}
return res;
}
以上题目其他解题思路请参考: https://www.jianshu.com/p/a3531d3d8196
2. 堆相关
1.1 题目类型以及做题小套路
这里的堆其实指的是PriorityQueue， PriorityQueue是通过完全二叉树（complete binary tree）实现的小顶堆，它是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator 在队列实例化的时排序。
PriorityQueue中的方法:
- offer(E e) 将指定的元素插入此优先级队列。
- peek() 获取但不移除此队列的头；如果此队列为空，则返回 null。操作的时间复杂度为 O(1)
- poll() 获取并移除此队列的头，如果此队列为空，则返回 null。操作的时间复杂度为 log(N)
1.2 Leetcode实例
q215 数组中的第K个最大元素
/**
* TopK问题
*
* 采用堆的方法：
* 1. 维护一个K大小的最小堆
* 2. 将数组中元素按顺序push进入堆
* 3. push时，如果堆中元素小于K个，则新元素直接进入堆；
* 否则，如果堆顶小于新元素，则弹出堆顶，将新元素加入堆
*
* 通过该操作，我们可知，最终堆中的K个元素，是最大的K个元素(因为任何比较小的元素，都会被弹出堆顶)，且堆的顶部就是要求的第K大的数。
* @param nums
* @param k
* @return
*/
public int findKthLargestTwo(int[] nums, int k){
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for (int num:nums){
priorityQueue.add(num);
if (priorityQueue.size()>k){
priorityQueue.remove();
}
}
return priorityQueue.remove();
}
q347 前K个高频元素
/**
* 使用PriorityQueue
* 1. 建立Hashmap对元素计算频率
* 2. 通过重新排序方式建立size为k的堆，遍历到最后k大小的堆是目标结果
* 3. 将堆转化为int[]
* @param nums
* @param k
* @return
*/
public static int[] topKFrequentTwo(int[] nums, int k){
HashMap<Integer, Integer> frequency = new HashMap<>();
//统计频率
for (int num:nums){
frequency.put(num,frequency.getOrDefault(num,0)+1);
}
PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return frequency.get(o1)-frequency.get(o2);
}
});
for (int num:frequency.keySet()){
heap.add(num);
if (heap.size()>k){
heap.remove();
}
}
int[] res = new int[k];
//输出结果
for (int i=k-1;i>=0;i--){
res[i] = heap.remove();
}
return res;
}
以上题目其他解题思路请参考: https://www.jianshu.com/p/d1644812af95
