刷题总结

一些刷题过程中的心得，记录一下…

1. 【LC. 1438】通过两个单调队列，可以在特定场景（滑窗）下，实现极大值和极小值的查询；

2. 【LC. 1798】排序后的动态规划思想，结合连续性延申特性，即：(i, j)新增x后(i + x, j + x)，只需j >= i +x；

3. 【LibreOJ. 10147】数组成环时，可考虑数组延长一倍处理（0, n - 1）-> (n, 2n - 1)；

4. 【Luogu. P2871】0-1背包、完全背包

   • 虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上角，根本不影响dp[i][j]公式的推导！
   • 背包问题里，两个for循环的先后循序是非常有讲究的，理解遍历顺序其实比理解推导公式难多了。
   • 一维解法中，为什么倒叙才能只放一次（0-1背包）？为什么顺序会被放多次（完全背包）？

   先遍历物品，再遍历背包

   先遍历背包，再遍历物品

5. 【LC. 1001】N x N矩阵中，两条“对角线”相同，指相同斜率：abs(x1-x2)/abs(y1-y2)==1，即abs(x1 - x2) == abs(y1 - y2)；