【leetcode】376. 摆动序列
题目内容 376. 摆动序列 思路分析 方法一：贪心 参考资料1 参考资料2 参考资料3 贪心策略：只选极值点，而忽略中间的所有点。 可以贪的原因：只选极值点，可以增大后续元素被选中为摆动序列的概率。详见参考资料2和3中的图。 实际实现时，只需记录极值点的个数。可以按照参考资料1，默认最右端有一个极值点，最左端（...
【leetcode】152. 乘积最大子数组
题目内容 152. 乘积最大子数组 思路分析 方法一：动态规划 本题与53. 最大子序和类似，但是本题是乘法运算，因此nums[i]的最大乘积不一定依赖于前一个数字（如[-1, 2, -3, 4]）。因此需要利用以下关系来进行动态规划： 当前最大值 = max(上一个数的最大值*当前数, 上一个数的最小值*当前数...
【leetcode】53. 最大子序和
题目内容 53. 最大子序和 思路分析 本题比较简单，可使用动态规划完成 方法一：动态规划 最大子序列和有以下特征： nums[i]的最大子序列和等于max(nums[i-1]的最大子序列和加nums[i], nums[i]) 因此nums[i]可利用nums[i-1]的计算结果，即可进行动态规划。 使用动态规划...
【leetcode】42. 接雨水
题目内容 42. 接雨水 思路分析 本题的总体思路为从第二个柱子起，判断每个柱子左右两边柱子的最大高度，然后max(0, min(左右两边的最大高度)-当前柱子高度)即为当前柱子可以装的水量。 方法一：动态规划 参考资料（其中的解法3） 利用当前柱子及其左边所有柱子的最大高度max_left_height=max...
【leetcode】309. 最佳买卖股票时机含冷冻期
题目内容 309. 最佳买卖股票时机含冷冻期 思路分析 本题也是股票系列的一道题目。题目中提到： 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 看到状态这个词就很明显的想到动态规划了（外加股票系列本来就动态规划用的多），虽然最后用的状态不是这个... 本题是自己定了状态仔细推导以后发现不对劲，又...
【leetcode】188. 买卖股票的最佳时机4
题目内容 188.买卖股票的最佳时机4 思路分析 本题是123. 买卖股票的最佳时机3 的更一般化，可直接由股票问题3的题解改编而来。 方法：动态规划 和股票问题3类似，使用一个大小为2k的数组cash来存储每一天的状态，令j为0,2,4,6...，则下标为j的元素代表某天买过j/2 + 1次，卖过j/2次；下标...
【leetcode】123. 买卖股票的最佳时机3
题目内容 123. 买卖股票的最佳时机3 思路分析 本题使用了动态规划的方法，状态比较多，比较难想到。 方法一：动态规划 参考链接1，参考链接2 每天交易完成后有5种状态： -1 不曾交易过 0 买过一次 1 买过一次，卖过一次 2 买过两次，卖过一次 3 买过两次，卖过两次 因为状态-1不会对现金产生影响，因此...
【leetcode】122. 买卖股票的最佳时机2
题目内容 122. 买卖股票的最佳时机2 思路分析 本题是股票系列的第二题，似乎一共有五六道题，做完以后就可以去炒股发家致富了🤣。 本题共有三种思路，拟人（方法一）、动态规划（方法二和三）和贪心（方法四）。其中方法一感觉也可以叫贪心。 感觉拟人和贪心比较容易想到，而动态规划，特别是二维动态规划，思路从何而来？感觉...
【leetcode】121. 买卖股票的最佳时机
题目内容 121. 买卖股票的最佳时机 思路分析 本题看起来很简单，但是自己做就是怎么都做不出来...自闭ing😶 本题共有两种思路，动态规划（方法一和方法二）和单调栈（方法三）。 方法一：动态规划 参考链接 选用动态规划的原因： 包含了重叠的子问题，买入和卖出股票的最佳时机是由之前的状态决定的，而之前的状态又是...