动态规划四+单调栈

6/28

T84柱状图中最大的矩形

1、和接雨水差不多，融合前两个情况后代码可以简略很多

2、代码如下：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.insert(heights.begin(), 0); // 数组头部加入元素0
        heights.push_back(0); // 数组尾部加入元素0
        st.push(0);
        int result = 0;
        for (int i = 1; i < heights.size(); i++) {
            while (heights[i] < heights[st.top()]) {
                int mid = st.top();
                st.pop();
                int w = i - st.top() - 1;
                int h = heights[mid];
                result = max(result, w * h);
            }
            st.push(i);
        }
        return result;
    }
};

T42 接雨水

1、大名鼎鼎的面试题啊，不记得是腾讯华为还是阿里反正知乎小红书上都刷到过很多次了，因此也熟悉解法咳咳

2、这题双指针可以暴力解，代码还短一些，但最优解还是单调栈

3、代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2) return 0; // 可以不加
        stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度
        st.push(0);
        int sum = 0;
        for (int i = 1; i < height.size(); i++) {
            if (height[i] < height[st.top()]) {     // 情况一
                st.push(i);
            } if (height[i] == height[st.top()]) {  // 情况二
                st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。
                st.push(i);
            } else {                                // 情况三
                while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while
                    int mid = st.top();
                    st.pop();
                    if (!st.empty()) {
                        int h = min(height[st.top()], height[i]) - height[mid];
                        int w = i - st.top() - 1; // 注意减一，只求中间宽度
                        sum += h * w;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
};

T503下一个更大元素2

1、和每日温度那题很像，关键用一下循环数组：将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就行

2、代码如下：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        // 拼接一个新的nums
        vector<int> nums1(nums.begin(), nums.end());
        nums.insert(nums.end(), nums1.begin(), nums1.end());
        // 用新的nums大小来初始化result
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;


        // 开始单调栈
        stack<int> st;
        st.push(0);
        for (int i = 1; i < nums.size(); i++) { 
            if (nums[i] < nums[st.top()]) st.push(i); 
            else if (nums[i] == nums[st.top()]) st.push(i);
            else { 
                while (!st.empty() && nums[i] > nums[st.top()]) {
                    result[st.top()] = nums[i];
                    st.pop();
                }
                st.push(i);
            }
        }
        // 最后再把结果集即result数组resize到原数组大小
        result.resize(nums.size() / 2);
        return result;
    }
};

6/27

【单调栈专题】

T496下一个更大元素1

1、对比上一题，直接用map，简单高效，注意前提是题干里无重复的数组

2、思路拆解： 情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况 此时满足递增栈（栈头到栈底的顺序），所以直接入栈

情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况 如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于

情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况 此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。 判断栈顶元素是否在nums1里出现过，（注意栈里的元素是nums2的元素），如果出现过，开始记录结果

3、代码如下：

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(), -1);
        if (nums1.size() == 0) return result;


        unordered_map<int, int> umap; // key:下标元素，value：下标
        for (int i = 0; i < nums1.size(); i++) {
            umap[nums1[i]] = i;
        }
        st.push(0);
        for (int i = 1; i < nums2.size(); i++) {
            if (nums2[i] < nums2[st.top()]) {           // 情况一
                st.push(i);
            } else if (nums2[i] == nums2[st.top()]) {   // 情况二
                st.push(i);
            } else {                                    // 情况三
                while (!st.empty() && nums2[i] > nums2[st.top()]) {
                    if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
                        int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
                        result[index] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

T739每日温度

1、栈里存储下标i即可，不必存具体内容

2、只有递增的时候，栈里要加入一个元素i的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i

3、代码如下：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        // 递增栈
        stack<int> st;
        vector<int> result(T.size(), 0);
        st.push(0);
        for (int i = 1; i < T.size(); i++) {
            if (T[i] < T[st.top()]) {                       // 情况一
                st.push(i);
            } else if (T[i] == T[st.top()]) {               // 情况二
                st.push(i);
            } else {
                while (!st.empty() && T[i] > T[st.top()]) { // 情况三
                    result[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};

6/26

T516 最长回文子序列

1、注意子串和子序列的区别。若s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;若s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。加入s[j]的回文子序列长度为dp[i + 1][j]。加入s[i]的回文子序列长度为dp[i][j - 1]。即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

2、这是动态规划专题最后一题！总体思路可类比上题，改变不大

3、代码如下：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][s.size() - 1];
    }
};

【非常重要】T647 回文子串

1、这一题是罕见的布尔类型的dp数组，和以往所有动态规划的套路都有所不同，具体和回文串的几何性质也很有关

2、dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。注意，初始化时均为false

3、关键：如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。 所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的

4、代码如下：

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};

5、双指针法有待复习，本题可用，且相对简易

6/25

【重要】T72 编辑距离

1、这一题我除了非常繁琐且可能错误的先找出最长公共子序列+对应切割+分段根据每段size不同计算增删替换一个个叠加数目外没有想到好的思路，查看题解时发现是很经典的需要见识一遍的题目，有极其巧妙的解法

2、dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。这一题再次说明：不论看起来多复杂的题目，对于动态规划而言，往往都可以针对整体处理，不必深入到具体细节（例如哪些字符相等），全面深入细节意味着可能走偏了

3、摘录分析： if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？ 操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。 即 dp[i][j] = dp[i - 1][j] + 1; 操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。 即 dp[i][j] = dp[i][j - 1] + 1;

word2添加一个元素，相当于word1删除一个元素，例如 word1 = “ad” ，word2 = “a”，word1删除元素’d’ 和 word2添加一个元素’d’，变成word1=”a”,， 最终的操作数是一样的。

操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增删加元素。只需要一次替换的操作，就可以让 word1[i - 1] 和 word2[j - 1] 相同。所以 dp[i][j] = dp[i - 1][j - 1] + 1;

综上，当 if (word1[i - 1] != word2[j - 1]) 时取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

4、代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
        for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

T583 两个字符串的删除操作

1、这一题当心，本质是和T1143最长公共子序列相同，而非和T718最长重复子数组相同，因为删除是任意的，可以让不连贯的公共字符也合并为连贯相等的，没有连续限制，而子序列又包含了子数组

2、删干净后，两个单词的size分别减去公共部分长度就是我们想要的最少次数

3、代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
        for (int i=1; i<=word1.size(); i++){
            for (int j=1; j<=word2.size(); j++){
                if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;
    }
};

6/24

【重要，困难级别】T115 不同的子序列

1、这一题不能简单用 //dp[i][j]代表在s[0…i]中t[0…j]出现的个数 if(s[i] == t[j]){ dp[i][j] = dp[i-1][j-1]; }
来处理，因为即便s[i] == t[j]，除了之前的每个解法都正确，还可能出现s中其他位置的字母等于s[i]，而左侧队列又恰好有t的上一层的子序列，这样便会出现无法统计数目的许多新解，故此思路错误

2、本题若非子序列，而为连续序列，可用KMP求解，待探究

3、关键：dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]

4、代码如下：

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
        for (int i = 0; i < s.size(); i++) dp[i][0] = 1;
        for (int j = 1; j < t.size(); j++) dp[0][j] = 0;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 1; j <= t.size(); j++) {
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.size()][t.size()];
    }
};

5、这一题的初始化很重要，对于dp[i][0]或反过来，由于对应的是数值减一的坐标，所以实际上相当于空字符串，而空集也是任何集合的子集

6、刚才又思考了一下，本题其实不存在【结尾与结尾】的卡死，写成这样是因为要合理描述子序列范围和需要拟合的字符范围。这一题和最简单的背包问题有异曲同工之处：最后一个元素取或不取，因此想清楚后实际没必要归为困难级别，还挺清晰的

T392 判断子序列

1、这一题看到就想到双指针法，由于子序列无关连续，因此只要遇见字母匹配的就往后推进，假如一直到母序列结束也未匹配完全，则返回false。注意边界调节，尤其是子序列为零时，为一切母序列的子序列

2、双指针代码如下：

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.size() == 0)
            return true;
        int l = 0;
        int r = 0;
        while(r < t.size()){
          if(s[l] == t[r]){
            l++;
            r++;
          }else{
            r++;
          }
          if(l == s.size())
              return true;



        }
            return false;
    }
};

3、这一题的动态规划思路非常独特，可以后续深入研究——少见地将字母类型也放入二维dp数组中进行处理：令 f[i][j] 表示字符串 t 中从位置 i 开始往后字符 j 第一次出现的位置。在进行状态转移时，如果 t 中位置 i 的字符就是 j，那么 f[i][j]=i，否则 j 出现在位置 i+1 开始往后，即 f[i][j]=f[i+1][j]，因此我们要倒过来进行动态规划，从后往前枚举 i

4、动态规划解法如下：

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(), m = t.size();


        vector<vector<int> > f(m + 1, vector<int>(26, 0));
        for (int i = 0; i < 26; i++) {
            f[m][i] = m;
        }


        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t[i] == j + 'a')
                    f[i][j] = i;
                else
                    f[i][j] = f[i + 1][j];
            }
        }
        int add = 0;
        for (int i = 0; i < n; i++) {
            if (f[add][s[i] - 'a'] == m) {
                return false;
            }
            add = f[add][s[i] - 'a'] + 1;
        }
        return true;
    }
};

6/23

T53 最大子序和

1、这一题之前有贪心解法，但贪心解法虽然简洁，理解难度却比动态规划大

2、动态规划解法中，赋值dp[i]需要相当谨慎：既然是连续的，就要卡死结尾；而我又想要最大和，因此可以只要一个结尾，也可以加上左侧部队一起。这样万一左侧总和为负，就可以抛弃之

3、初始元素和result的初始赋值很重要，要考虑nums只有一个元素、初始元素为负数的情况，即便全数组都为负数，result也可以取最小的一个元素，而该元素可能为nums[0]

4、代码如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(),0);
        int result = nums[0];

        if(nums.size() == 1)
            return result;
        //dp[i]表示数组[0...i]之间的以nums[i]结尾的具备最大和的连续子数组
        dp[0] = nums[0];
        for(int i = 1;i < nums.size();i++){
            dp[i] = max(nums[i],nums[i] + dp[i-1]);
            if(dp[i] > result)
              result = dp[i];
        }
            return result;
    }
};

T1035 不相交的线

1、不相交意味着：所有组合之间要么两个元素都大于对方两者，要么两个元素都小于

2、和上一题类似，若相等，加一；不相等，只取其一更新max。重要：之所以只取其一，是因为若新的两个元素都取，且队伍统一在左侧，必然会出现两线交叉情况，故舍弃

3、代码如下：

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
      vector<vector<int>> dp(nums1.size() + 1,vector<int>(nums2.size() + 1,0));
        for(int i = 1;i <= nums1.size();i++){
            for(int j = 1;j <= nums2.size();j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;

                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
              return dp[nums1.size()][nums2.size()];
        }
    };

T1143 最长公共子序列

1、这一题很适合用来养成良好习惯，手搓时没想清楚边界问题一下就会暴露出来。首先，dp[i][j]代表的是长度为i j的两个数组的最长公共子序列的长度，那么坐标最大值就是i-1 j-1，这才是当前需要比较是否相等的值；其次，遍历时也应该把结尾遍历到，而非常见的取小于号；最后，dp[0][0]是无意义的，没有坐标为-1的元素，这也是最终循环统一右移一位的原因

2、不要死套公式，这一题既没有连续的要求，又无单调性要求，毫无必要卡死“以…为结尾”这一要求，这样的序列是可以灵活跳脱的

3、当心：并不是不等就不管它或直接赋值上一层，即便最后两个元素不等，它们也可以分别加入与对面序列进行灵活取公，也就是dp[i-1][j] dp[i][j-1]，这点思考很重要，容易漏掉。顺便，string是可以直接按照char取坐标位的，无需拆入新的容器，也可以直接调用size()方法

4、代码如下：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1,vector<int>(text2.size() + 1,0));
        //dp[i][j]代表在text1[0...i-1]和text2[0...j-1]中最长公共子序列的长度
        for(int i = 1;i <= text1.size();i++){
            for(int j = 1;j <= text2.size();j++){
                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }

            }
        }
        return dp[text1.size()][text2.size()];
    }
};