题解思路
塔子哥希望找到连续 x 天内可以获得最多金币的方案。为了实现这一目标,我们的日历数据是一个长度为 n 的数组 d,其中每个元素表示每个月的天数。由于塔子哥可以跨越到下一年的第一个月,因此我们需要考虑跨年情况。为了解决这个问题,我们采用了以下思路:
-
双倍日历数组:将日历数组 d 复制一份,形成一个长度为 2n 的数组。这一做法确保我们可以在任何地方找到长度为 x 的连续天数,并且能够平滑地处理跨年情况。
-
滑动窗口算法:我们通过滑动窗口的方式来计算在不同起点下,连续 x 天可以获得的金币总数。窗口的初始位置从 0 开始,每次移动一格,尝试不同的起点。
-
动态调整窗口:在窗口滑动过程中,维护当前窗口中的天数和金币总和。如果当前窗口内的天数和大于 x,则从左侧移除天数,直到窗口中的天数和小于等于 x。