LeetCode 151-155

151. 翻转字符串里的单词

class Solution {
    public String reverseWords(String s) {
        String[] splits = s.split(" ");
        List<String> res = new ArrayList<>();
        for (String str : splits) {
            if (!"".equals(str)) {
                res.add(str);
            }
        }
        Collections.reverse(res);
        StringBuilder sb = new StringBuilder();
        for (String str : res) {
            sb.append(str + " ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
}

152. 乘积最大子数组

记录以i为结尾的子数组乘积最大值和乘积最小值。那么最大值一定是nums[i] ， nums[i] * maxDp[i - 1] ， nums[i] * minDp[i-1] 三者较大值。 最小值一定是三者较小值。 然后找到最大的maxDp[i]就是答案。

class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int res = nums[0];
        int[] maxDp = new int[nums.length];
        int[] minDp = new int[nums.length];
        maxDp[0] = minDp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxDp[i] = Math.max(nums[i], Math.max(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]));
            minDp[i] = Math.min(nums[i], Math.min(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]));
            res = Math.max(res, maxDp[i]);
        }
        return res;
    }
}

153. 寻找旋转排序数组中的最小值

这道题mid只能和hi去比较，因为如果mid比hi大，那么最小值一定在mid右边。如果mid比hi小，最小值一定在mid左边（包含mid）。
刚开始区间一定存在翻转，缩小区间之后，可能区间就不存在翻转变成单调递增的了。
如果mid去和lo比较，如果mid比lo大，区间存在翻转的情况下，最小值在mid右边，区间不存在翻转的情况下，最小值在mid左边，无法统一情况。

class Solution {
    public int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[hi]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return nums[lo];
    }
}

154. 寻找旋转排序数组中的最小值 II

class Solution {
    public int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[hi]) {
                lo = mid + 1;
            } else if (nums[mid] < nums[hi]) {
                hi = mid;
            } else {
                hi--;
            }
        }
        return nums[lo];
    }
}

155. 最小栈

使用minstack来记录最小栈，每次push的时候都比较x与最小栈的栈顶谁小，如果栈顶的元素更小，那么把栈顶的元素再入栈一次，保证最小栈的栈顶存的一定是最小的数。

public class MinStack {
    Deque<Integer> stack, minStack;
    public MinStack() {
        stack = new ArrayDeque();
        minStack = new ArrayDeque<>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        stack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }

}