[LC] 2944 Minimum Number of Coins for Fruits

Java

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/minimum-number-of-coins-for-fruits/">Minimum Number of Coins for Fruits</a>
 * 队列；数组；动态规划；单调队列；堆（优先队列）
 */
class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offerFirst(new int[]{n, 0});
        for (int i = n - 1; i >= 0; i--) {
            while (queue.peekLast()[0] >= 2 * i + 3) {
                queue.pollLast();
            }
            int cur = queue.peekLast()[1] + prices[i];
            while (queue.peekFirst()[1] >= cur) {
                queue.pollFirst();
            }
            queue.offerFirst(new int[]{i, cur});
        }
        return queue.peekFirst()[1];
    }
}

Go

func minimumCoins(prices []int) int {
    n := len(prices)
    queue := [][2]int{{n, 0}}

    for i := n - 1; i >= 0; i-- {
        for len(queue) > 0 && queue[len(queue)-1][0] >= 2*i+3 {
            queue = queue[:len(queue)-1]
        }
        cur := queue[len(queue)-1][1] + prices[i]
        for len(queue) > 0 && queue[0][1] >= cur {
            queue = queue[1:]
        }
        queue = append([][2]int{{i, cur}}, queue...)
    }

    return queue[0][1]
}

JavaScript

var minimumCoins = function (prices) {
    const n = prices.length;
    const queue = [];
    queue.push([n, 0]);
    for (let i = n - 1; i >= 0; i--) {
        while (queue[queue.length - 1][0] >= 2 * i + 3) {
            queue.pop();
        }
        let cur = queue[queue.length - 1][1] + prices[i];
        while (queue[0][1] >= cur) {
            queue.shift();
        }
        queue.unshift([i, cur]);
    }
    return queue[0][1];
};

PHP

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function minimumCoins(array $prices): int {
        $n = count($prices);
        $queue = [];
        array_push($queue, [$n, 0]);
        for ($i = $n - 1; $i >= 0; $i--) {
            while (end($queue)[0] >= 2 * $i + 3) {
                array_pop($queue);
            }
            $cur = end($queue)[1] + $prices[$i];
            while (reset($queue)[1] >= $cur) {
                array_shift($queue);
            }
            array_unshift($queue, [$i, $cur]);
        }
        return reset($queue)[1];
    }
}