徒步旅行中的补给问题

队列

    public static int solution(int n, int k, int[] data) {int minMoney = 0;Queue<Integer> ready = new LinkedList<>();int minValue;for (int i = 0; i < n; i++) {// 当前站点加入readyready.add(data[i]);// 如果ready大于k，就将最先进入的站点价格删除if (ready.size() > k) {ready.poll();}// 找到最小值，时间复杂度为O(k)minValue = findMin(ready);minMoney += minValue;}return minMoney;}// 找到队列中的最小值private static int findMin(Queue<Integer> queue) {int min = Integer.MAX_VALUE;for (int value : queue) {min = Math.min(min, value);}return min;}

优化
可以使用 单调队列（Monotonic Queue） 来优化找到窗口最小值的部分：

单调队列维护窗口内的元素顺序，使得队列的最前端始终是窗口的最小值。
每次加入新元素时，将比它大的队列元素移除，保持队列单调递增。

单调队列

import java.util.Deque;
import java.util.LinkedList;public class Main {public static int solution(int n, int k, int[] data) {int minMoney = 0;// 单调队列，用于存储当前窗口的索引，队列中存储的数据是单调递增的Deque<Integer> deque = new LinkedList<>();for (int i = 0; i < n; i++) {// 如果队列首部的索引不在窗口范围内，移除它if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {deque.pollFirst();}// 从队列尾部移除所有比当前元素大的值// 这样可以保证队列中元素的单调性（从小到大）while (!deque.isEmpty() && data[deque.peekLast()] > data[i]) {deque.pollLast();}// 将当前索引加入队列deque.offerLast(i);// 累加当前窗口的最小值（队列首部存储的是最小值的索引）minMoney += data[deque.peekFirst()];}return minMoney;}public static void main(String[] args) {// Add your test cases hereSystem.out.println(solution(5, 2, new int[] { 1, 2, 3, 3, 2 }) == 9);}
}

ps：代码都是GPT给出的，自己尝试用贪心总是有点问题