20200810筆記.696.121

每日一題：
696，計數二進制子串
’想用棧，但是沒用明白
官方的解法很好，還很好理解，統計相鄰的相同字元的頻數，把頻數當做元素形成陣列，然後根據相鄰兩個元素中的最小值，就可以知道原來的這兩個字串能形成的符合條件子串數量了。

121.股票買賣
1.
雖然是想做動態規劃，但是這道題還有個解法是單調棧，雖然有些強行
單調棧可以用來高效率得到一個元素左右兩側比他大或小的元素，
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/c-li-yong-shao-bing-wei-hu-yi-ge-dan-diao-zhan-tu-/

2.
本題的思想是可以由動態規劃得到的

public int maxProfit(int[] prices) {
		int minPrice = Integer.MAX_VALUE;
		int maxProfit = 0;
		for(int i = 0;i<prices.length;i++) {
			if(prices[i]<minPrice) {
				minPrice = prices[i];
			}else if(prices[i]-minPrice > maxProfit) {
				maxProfit = prices[i] - minPrice;
			}
		}return maxProfit;
		
    }

這是優化過得思想，只進行一次遍歷，要是碰到更小的，就更新最小值，要是碰到更大的，能讓maxProfit發生變化的，就更新最大利潤，從前往後的順序，也避免了賣出在買入之前的不合法情況。

如果根據dp來分析
開始這道題我一直在想是不是01揹包問題，只取其中兩項爲1，其餘爲0，後來發現不會用01揹包的狀態表示來類推這個題的，（就是說，不選第i個物品的情況可以由f{i-1}表示，但是選了第i個物品的如何表示我沒有想好）他的這個狀態遞推方程就好描述了，終究還是要記錄最小值的。