力扣Hot100每日N题（15~16）

155. 最小栈

class MinStack {private Deque<Integer> st;private Deque<Integer> minSt;public MinStack() {st = new LinkedList<>();minSt =  new LinkedList<>();}public void push(int val) {st.offerLast(val);if(!minSt.isEmpty()) minSt.offerLast(Math.min(val, getMin()));else minSt.offerLast(val);}public void pop() {st.removeLast();minSt.removeLast();}public int top() {return st.peekLast();}public int getMin() {return minSt.peekLast();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

152. 乘积最大子数组

动态规划版

class Solution {public int maxProduct(int[] nums) {int n = nums.length, ans = nums[0];int ma = nums[0], mi = nums[0];for(int i = 1; i < n; i++){int x = ma*nums[i], y = mi*nums[i];ma = Math.max(nums[i], Math.max(x, y));mi = Math.min(nums[i], Math.min(x, y));ans = Math.max(ans, ma);}return ans;}
}

贪心版
区间一定不会包含0（除非全0）
枚举每个不包含0的区间即可

class Solution {public int maxProduct(int[] nums) {int ans = Integer.MIN_VALUE, pre = 1, suf = 1, n = nums.length;for(int i = 0, j = n-1; i < n; i++, j--){pre *= nums[i];suf *= nums[j];ans = Math.max(Math.max(ans, nums[i]), Math.max(pre, suf));if(nums[i] == 0) pre = 1;if(nums[j] == 0) suf = 1;}return ans;}
}