剑指offer-栈

首先学习一下Java中栈的常用Constructor和Method

JZ30 包含min函数的栈

题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

思路一

这题不难想到是使用第二个栈，使用一个栈记录进入栈的元素，正常进行push、pop、top操作，使用第二个栈来返回最小值，首先我想到的是使用第二个栈有序的保存所有元素，min操作直接返回这个栈的最顶端元素即可。

import java.util.*;
import java.util.Stack;

public class Solution {

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> stackMin = new Stack<>(); 

    public void push(int node) {
        stack.push(node);
        if(!stackMin.empty()) {
            if(node > stackMin.peek()) {
                Stack<Integer> temp1 = new Stack<>();
                while(!stackMin.empty() && node > stackMin.peek()) {
                    temp1.push(stackMin.pop());

                }
                stackMin.push(node);
                while(!temp1.empty()) {
                    stackMin.push(temp1.pop());
                }
            } else {
                stackMin.push(node);
            }
        } else {
            stackMin.push(node);
        }
    }
    
    public void pop() {
        if (stack.empty()) {
            return ;
        } else {
            int value = stack.pop();
            Stack<Integer> stackTemp = new Stack<>(); 
            while (!stackMin.empty()) {
                if (stackMin.peek() == value) {
                    stackMin.pop();
                    break;      // 遇到相同的元素，就需要跳出while循环，以免重复删除值
                } else {
                    stackTemp.push(stackMin.pop());
                }
            }
            while (!stackTemp.empty()) {
                stackMin.push(stackTemp.pop());
            }
        }
    }
    
    public int top() {
        if (!stack.empty()) {
            int topValue = stack.peek();
            return topValue;
        } 
        return 0;
    }
    
    public int min() {
        if(!stack.empty())
            return stackMin.peek();
        return 0;
    }
}

第一种思路实际上做了很多冗余的功能，因为并不需要给第二个栈排序，具体见思路二。

思路二

还是双栈，使用第一个栈记录进入栈的元素，正常进行push、pop、top操作，使用第二个栈记录每次push进入的最小值；每次第二个栈push元素的时候与第二个栈的栈顶元素比较，若是较小，则进入第二个栈，若是较大，则第二个栈的栈顶元素再次入栈，因为即便加了一个元素，它依然是最小值。于是，每次访问最小值即访问第二个栈的栈顶。

import java.util.Stack;
public class Solution {
    //用于栈的push 与 pop fast-template
    Stack<Integer> s1 = new Stack<Integer>();
    //用于存储最小min
    Stack<Integer> s2 = new Stack<Integer>();
    public void push(int node) {
        s1.push(node);
        //空或者新元素较小，则入栈
        if(s2.isEmpty() || s2.peek() > node)
            s2.push(node);
        else
            //重复加入栈顶
            s2.push(s2.peek());
    }
    public void pop() {
        s1.pop();
        s2.pop();
    }
    public int top() {
        return s1.peek();
    }
   public int min() {
        return s2.peek();
   }
  }

思路三

使用一个栈，入栈和出栈的每个元素变成一个结构体，结构体中包（含元素值，栈内最小值），每次push的时候都更新栈内最小值。

• top获取结构体第一个值
• min获取结构体第二个值
• pop删除栈顶结构体
• push分两种情况
  • 栈为空时，直接push结构体，（x，最小值也是x）
  • 栈不为空，比较栈顶元素y与结构体x,取最小值压入栈（x,min(x,y)）

import java.util.Stack;

public class Solution {
    //用于栈的push 与 pop fast-template
    Stack<stackElemt> s = new Stack<stackElemt>();

    public class stackElemt {
        private int value;
        private int min;

        public stackElemt(int value, int min) {
            this.value = value;
            this.min = min;
        }

    }

    public void push(int node) {
        if (s.isEmpty()) {
            s.push(new stackElemt(node, node));
        } else {
            if (node > s.peek().min) {
                s.push(new stackElemt(node, s.peek().min));
            } else {
                s.push(new stackElemt(node, node));
            }
        }
    }

    public void pop() {
        s.pop();
    }

    public int top() {
        return s.peek().value;
    }
    public int min() {
        return s.peek().min;
    }

}

JZ31 栈的压入、弹出序列

描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

思路

双指针分别指向压入序列和弹出序列首位，一直将压入序列压入栈，每压入一个元素，压入序列指针后移，判断栈顶元素与弹出序列元素是否相等，不相等继续压入，相等则弹出栈顶元素并弹出序列指针后移，并继续判断栈顶元素是否与弹出序列指针元素相等，若相等继续弹出栈顶元素，不相等就继续压入元素。等待压入序列全部压入进栈，然后将所有元素出栈，如果匹配弹出序列，则返回true，否则返回false。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型一维数组 
     * @param popV int整型一维数组 
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        if(pushV.length == 0)   return true;
        Stack<Integer> s = new Stack<Integer>();
        int i = 0, j = 0;
        for (; i < pushV.length; i++) {
            s.push(pushV[i]);
            while(!s.empty() && s.peek() == popV[j]) {
                s.pop();
                j++;
            }
        }
        boolean result = true;
        // 判断弹出序列和栈内元素完全匹配
        if(j == pushV.length) {
            result = true;
        } else {
            result = false;
        }
        return result;
        
    }
}

JZ73 翻转单词序列

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

示例：

Input: "nowcoder. a am I"
Output: "I am a nowcoder."

思路

可以发现，只有词序倒置，每个单词字母顺序正确，只需要用栈的特性，先存储每个单词字符串，然后再输出就可实现翻转单词序列效果。

值得注意的是Java中字符串String自带很多method能够实现很多功能，譬如：

• String.split(String regex) –– Splits this string around matches of the given regular-expression.
• + operation can link string directly.

import java.util.*;
public class Solution {
    public String ReverseSentence(String str) {
        if(str == null) return null;
        String outputStr;
        String[] tempStr = str.split(" ");
        Stack<String> stack = new Stack<String>();
        for(String temp : tempStr) {
            stack.push(temp);
        }
        outputStr = stack.pop();
        while(!stack.empty()) {
            outputStr = outputStr + " " + stack.pop();
        }
        return outputStr;
    }
}

JZ59 滑动窗口最大值

描述
给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。窗口大于数组长度或窗口长度为0的时候，返回空。
数据范围： 1≤n≤100001≤n≤10000，0≤size≤100000≤size≤10000，数组中每个元素的值满足 ∣val∣≤10000∣val∣≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)

思路一

暴力方法，遍历数组，然后每选取出窗口数组，并选取出窗口最大值，可行，但是时间复杂度是O(n*k)不满足时间复杂度要求

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @param size int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        // write code here
        // 窗口大于数组长度或窗口长度为0的时候，返回空。
        ArrayList<Integer> window = new ArrayList<Integer>();
        if (num.length < size || num.length == 0 || size == 0)  return window;

        // ArrayList<Integer> window = new ArrayList<Integer>();
        int numWindow = num.length - size + 1;

        for (int i = 0; i < numWindow; i++) {
            int[] subNum = new int[size];
            subNum = copyOfRange(num, i, i + size);
            window.add(selectMax(subNum));
        }
        return window;
    }

    public int selectMax(int[] num) {
        int max = num[0];
        for(int i = 0; i < num.length; i++) {
            // 三元运算符
            max = (max >= num[i]) ? max : num[i]; 
        }
        return max;
    }

    public int[] copyOfRange(int[] num, int start, int end) {
        // 包含start，不包含end
        int[] subNum = new int[end - start];
        for(int i = 0; i < (end - start); i++) {
            subNum[i] = num[start + i];
        } 
        return subNum;
    }
}

思路二

在暴力求解的过程中，我们发现子窗口右滑时，新进入的数字A如果比窗口内的其他数字都大，那么数字A之前的数字更最大值就没有关系了，在之后窗口滑动过程都是无用的，因为他们比A早离开子窗口，所以每次滑动窗口时，新增加的数字A与子窗口内的数字进行比较，将小于A的数字都去掉，如果A大于所有数字，就只需要数字A了。每次滑动窗口，还需要判断是否需要丢掉某个元素，因为这个元素可能已经不在子窗口内了。

要实现这样的功能，我们需要一个双向队列，这个队列尾端既能进新的数组下标又能删除数组下标，另一端进行读取数组下标，也能删除数组下标。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @param size int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        // write code here
        // 窗口大于数组长度或窗口长度为0的时候，返回空。
        ArrayList<Integer> window = new ArrayList<Integer>();
        if (num.length < size || num.length == 0 || size == 0)  return window;
        // 使用集合维护一个双向队列,队列中存储数组元素下表
        ArrayDeque<Integer> dq = new ArrayDeque<Integer>();
        // 先遍历一个子窗口
        for (int i = 0; i < size; i++) {
            // 去掉比自己先进队列且小于自己的元素的下标，然后对应数组下标再入队
            while (!dq.isEmpty() && num[dq.peekLast()] < num[i]) {
                dq.pollLast();
            }
            dq.add(i);
        }
        // 遍历后续数组元素
        for (int i = size; i < num.length; i++) {
            // 每移动一次子窗口，返回数组中添加一个值,添加的这个值是队列中的第一个数组下标对应num数组中的值
            window.add(num[dq.peekFirst()]);
            //每移动一次子窗口，队列中有可能需要移走对应下标，需要移走的下标一定在队列最前端
            if(!dq.isEmpty() && dq.peekFirst() < (i - size + 1))
                dq.pollFirst();
            // 加入新的值前，去掉比自己先进队列且小于自己的元素的下标，然后对应数组下标再入队
            while(!dq.isEmpty() && num[dq.peekLast()] < num[i]) {
                dq.pollLast();
            }
            dq.add(i);
        }
        window.add(num[dq.pollFirst()]);
        return window;
    }


}