📌 📄 内容摘要:
@ninijia 在 Leetcode每日一题练习 ------ 862. 和至少为 K 的最短子数组 中发帖
从Leetcode 每日一题练习继续讨论：
862. 和至少为 K 的最短子数组
862. Shortest Subarray with Sum at Least K
题解
本题求子数组的和满足大于等于K的全部子数组中长度最小的长度是多少。这种求子数组和的有关性质的题目首先可以想到使用前缀和来解决，但之前使用前缀和解题时是因为前缀和有一个很重要的性质即单调性，当所有数字均为非负数时前缀和是单调增的，因此我们可以根据题目要求来找到对应的下标，如同样是求子数组和至少为K的问题，若是单调增的前缀和，则根据下标为i对应的前缀和减去K的前缀和P来找到对应的小于等于P的前缀和对应的下标，即可知道所有子数组和至少为K的子数组。
但本题中存在负数，因此前缀和不是单调增的，这时可以考虑能否构造一个单调增的前缀和，则可使用单调栈来构造这样的前缀和，考虑栈顶前缀和的大小和新的前缀和的大小关系，若栈顶前缀...
────────── 链接信息 ──────────
🔗 论坛链接: linux.do
📎 访问地址: https://linux.do/t/topic/262200/1
─────────────────────────────
📢 来源：LINUX DO
