- to do
- before 13.4] Maximal Square
mark: improve using rotating array
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
// dp : maxSide[i][j] stores maximalSquare's side length who uses matrix[i][j] as rightMost corner
vector<vector<int>> maxSide(m, vector<int>(n, 0));
int ret = 0;
for (int i=0; i<m; ++i) {
maxSide[i][0] = matrix[i][0]-'0';
ret = max(ret, maxSide[i][0]);
}
for (int j=0; j<n; ++j) {
maxSide[0][j] = matrix[0][j]-'0';
ret = max(ret, maxSide[0][j]);
}
for (int i=1; i<m; ++i) {
for (int j=1; j<n; ++j) {
if (matrix[i][j]!='0') {
int m1 = maxSide[i][j-1], m2 = maxSide[i-1][j], minm = min(m1, m2);
maxSide[i][j] = minm + (matrix[i-minm][j-minm]-'0');
ret = max(ret, maxSide[i][j]);
}
}
}
return ret*ret;
}
- again Largest Rectangle in Histogram
- 1) 改进的暴力 O（n）?
- 最原始的暴力是从左往右遍历，当前ith whole bar为左界限，向右延伸找第一个矮于自己的； 算出面积。O（n^2）
- 或者另一种想法，最大矩形必然包含了某一个立柱的全部。所以遍历是向左右延伸，算用了当前立柱的最大面积。（所以当前立柱是rect内最低高度）
- 所以每一步想要知道lefti of 向左延伸遇到的第一个比自己矮的立柱，以及righti同理。所以
area = heights[i] * (righti-lefti-1)。 这里又有两种办法- dp 两遍遍历构建leftIndex[], rightIndex[]
-
用非递减stack来找lefti/righti
先说stack的办法：
- 所以每一步想要知道lefti of 向左延伸遇到的第一个比自己矮的立柱，以及righti同理。所以
- 考虑非递减的array【1,4,5,5,7,9】，如果算用了当前立柱的最大面积，很简单只需要从右往左遍历，记住incremental的宽度n-i，乘以height[i]得到面积。（虽然在重复值情况中，【n-2】的5不会得到最大值，但是最左边的重复值会保证捕捉最大值）
-
如果在1的基础上加上一个违反规律更小的6 => array【1,4,5,5,7,9,6】
===========我是启动画面(xia)感(che)的分割线==============
顺序的大人的看到了小矮红i的加入，之前的简单算法hold不住了，暂停下遍历来观察下:
发现在小矮红线以上的那些高柱其实找到了righti就是i，换而言之小矮成了高柱们一辈子的短板限制，sad；而小矮呢，它的lefti并不关心高柱们有多高多厉害，而是向左第一个比小矮还矮的柱子2hhh。
既然互不关心一拍即合，那么高柱们就退场了，但别漏了当maxArea的可能性啊，所以退场前算一下Area：height[self] * (i-lefti-1) where lefti = s.empty()? i : s.top().
退场结束。
终于又回到非递增的规则世界~可是退场的高柱会影响未来的面积记录突破吗？小矮说 不会的，即使高柱在，未来我右边的每个柱子往左延伸都要经过我这一关，别忘了我是他们的短板。
那好，别忘了所有柱子都要算面积，元素都是算了面积再被pop，意思是stack最后要清空。当然可以加一个while not empty{loop}，或者巧妙的
resume遍历
- 所以这道题和Maximal Rect相通之处就是可以把平面看做大矩阵，条形看做1，非条形看做0，寻找最大全1矩阵。
- reference
public:
// 暴力
int largestRectangleArea(vector<int>& heights) {
if (heights.empty()) return 0;
int n = heights.size();
vector<int> h(n+2, -1);
// left[i] gives the index of farthest reachable bar on the LHS
vector<int> left(n+1, -1);
vector<int> right(n+2, -1);
//往左找第一个比自己矮的
for (int i=1; i<=n; ++i) {
int k = i;
//比自己高就继续找
while (h[i] <= h[k-1]) k = left[k-1];
left[i] = k;
}
for (int i=n; i>0; --i) {
int k = i;
//比自己高就继续找
while (h[i] <= h[k+1]) k = right[k+1];
right[i] = k;
}
int ret = 0;
for (int i=1; i<=n; ++i) {
ret = max(ret, h[i]*(right[i]-left[i]+1));
}
return ret;
}
- 2) using stack
int largestRectangleArea(vector<int>& heights) {
int ret = 0, n = heights.size();
stack<int> s;
// want to calculate maxarea using the whole heights[i]
// meaning: extend farthest to left, find first bar < heights[i]; same to right
int i=0;
while (i<n) {
if (s.empty() || heights[i]>=heights[s.top()]) {
s.push(i++);
} else {
// calculate area of bar w/ heights[tp] as height
int tp = s.top();
s.pop();
int width = s.empty()? i : i-s.top()-1;
ret = max(ret, width*heights[tp]);
}
}
while (!s.empty()) {
// calculate area of bar w/ heights[tp] as height
int tp = s.top();
s.pop();
int width = s.empty()? i : i-s.top()-1;
ret = max(ret, width*heights[tp]);
}
return ret;
}
13.5] Best Time to Buy and Sell Stock III
lalala
开始忘记stockI解dp存的是当天卖会得到的收入，而非当前最佳收入。
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n<2) return 0;
// build dp1: dp1[i] gives maxProfit so far of period [0-i]
int minSoFar = prices[0], maxP = 0;
vector<int> dp1(n, -1);
for (int i=0; i<n; ++i) {
minSoFar = min(minSoFar, prices[i]);
maxP = max(maxP, prices[i] - minSoFar);
dp1[i] = maxP;
}
// build dp2: dp2[i] gives maxProfit so far of period [i-(n-1)]
int maxSoFar = prices[n-1];
maxP = 0;
vector<int> dp2(n, -1);
for (int i=n-1; i>=0; --i) {
maxSoFar = max(maxSoFar, prices[i]);
maxP = max(maxP, maxSoFar - prices[i]);
dp2[i] =maxP;
}
// dp2[n] = 0
dp2.push_back(0);
// build dp3:
int maxRet = INT_MIN;
for (int k=0; k<n; ++k) {
maxRet = max(maxRet, dp1[k] + dp2[k+1]);
}
return maxRet;
}
- naive recursive method
bool isInterleave(string s1, string s2, string s3) {
if (s3.size() != s1.size() + s2.size()) return false;
if (s2.empty()) return s1.compare(s3)==0;
if (s1.empty()) return s2.compare(s3)==0;
if (s1[0]!=s3[0] && s2[0]!=s3[0]) return false;
bool ret = false;
if (s1[0]==s3[0]) ret = ret || isInterleave( s1.substr(1, s1.size()-1), s2, s3.substr(1, s3.size()-1) );
if (s2[0]==s3[0]) ret = ret || isInterleave( s1, s2.substr(1, s2.size()-1), s3.substr(1, s3.size()-1) );
return ret;
}
- better dp
Make sure understand what the memo structure holds and where the bound is. Follow the equation at all time. Bug when I wasn't clear what the boundry means and another bug see comment below.
bool isInterleave(string s1, string s2, string s3) {
if (s1.size()+s2.size() != s3.size()) return false;
if (s3.empty()) return true;
int m = s1.size(), n = s2.size(), l = s3.size();
vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
dp[m][n] = true;
for (int i=m-1; i>=0; --i) dp[i][n] = dp[i+1][n] && s1[i]==s3[i+n];
for (int j=n-1; j>=0; --j) dp[m][j] = dp[m][j+1] && s2[j]==s3[m+j];
for (int i=m-1; i>=0; --i) {
for (int j=n-1; j>=0; --j) {
int k = i+j;
if (s3[k]==s1[i] || s3[k]==s2[j]) {
dp[i][j] = (s3[k]==s1[i] && dp[i+1][j]) ||
(s3[k]==s2[j] && dp[i][j+1]);
}
}
}
return dp[0][0];
}
