商店特別折扣的最終價格

1475。最終價格在商店有特別折扣

難度：簡單

主題：陣列、堆疊、單調堆疊

給你一個整數數組prices，其中prices[i]是商店中第i^個個商品的價格。

店內商品有特別折扣。如果您購買第 i^th 件商品，那麼您將獲得相當於價格[j]的折扣，其中 j 是滿足 j > 的最小索引。 i 且價格[j]

返回一個整數數組答案，其中answer[i]是您為商店第i^第件商品支付的最終價格，考慮到特別折扣。

範例1：

• 輸入： 價格 = [8,4,6,2,3]
• 輸出： [4,2,4,2,3]
• 說明：
  • 對於價格[0]=8的商品0，您將獲得相當於價格[1]=4的折扣，因此，您將支付的最終價格是8 - 4 = 4。
  • 對於價格[1]=4的商品1，您將獲得相當於價格[3]=2的折扣，因此，您將支付的最終價格為4 - 2 = 2。
  • 對於價格[2]=6的商品2，您將獲得相當於價格[3]=2的折扣，因此，您將支付的最終價格為6 - 2 = 4。
  • 對於第 3 項和第 4 項，您將不會獲得任何折扣。

範例2：

• 輸入： 價格 = [1,2,3,4,5]
• 輸出： [1,2,3,4,5]
• 說明：在這種情況下，對於所有商品，您將不會獲得任何折扣。

範例 3：

• 輸入： 價格 = [10,1,1,6]
• 輸出： [9,0,1,6]

約束：

• 1
• 1

提示：

1. 使用暴力破解：對於有循環的商店中的第 i 個商品，找到第一個滿足條件的位置 j 並應用折扣，否則折扣為 0。

解：

我們需要根據後續商品的價格小於或等於當前價格的情況來應用特殊折扣，我們可以使用暴力的方法。我們將迭代價格數組，並針對每個商品找到其後價格較低或相等的第一個商品。這可以透過嵌套循環來實現。我們可以利用堆疊來有效地追蹤商品的價格並應用特別折扣。

方法：

1. 堆疊方法:

   • 我們可以從左到右迭代價格數組。對於每件商品，我們將使用堆疊來追蹤尚未找到折扣的價格。
   • 對於每個價格，我們都會檢查它是否小於或等於堆疊頂部的價格。如果是這樣，那就意味著我們可以申請折扣。
   • 堆疊將儲存商品的索引，對於每個商品，我們將檢查當前價格是否大於堆疊中索引處的價格，這意味著沒有折扣。否則，透過從當前價格中減去相應的價格來應用折扣。

2. 邊緣情況：如果陣列中後面沒有任何商品的價格較小，則不套用折扣。

讓我們用 PHP 實作這個解：1475。最終價格在商店有特別折扣

<?php
/**
 * @param Integer[] $prices
 * @return Integer[]
 */
function finalPrices($prices) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$prices1 = [8, 4, 6, 2, 3];
$prices2 = [1, 2, 3, 4, 5];
$prices3 = [10, 1, 1, 6];

print_r(finalPrices($prices1)); // Output: [4, 2, 4, 2, 3]
print_r(finalPrices($prices2)); // Output: [1, 2, 3, 4, 5]
print_r(finalPrices($prices3)); // Output: [9, 0, 1, 6]
?>

解釋：

1. 初始化:

   • 建立一個與$prices大小相同的陣列$result，並將其初始化為0。

2. 外循環:

   • 循環遍歷索引 $i 處的每個價格，計算折扣後的最終價格。

3. 內循環:

   • 對於每個價格 $i，迭代後續價格 $j（其中 $j > $i）。
   • 檢查$prices[$j]是否小於或等於$prices[$i]。如果為 true，則設定 $discount = $prices[$j] 並退出內循環。

4. 最終價格計算：

   • 從 $prices[$i] 中減去找到的折扣並將結果儲存在 $result[$i] 中。

5. 回傳結果:

   • 處理完所有價格後，傳回最終結果陣列。

複雜：

• 時間複雜度：O(n²)（由於每個價格的巢狀循環）。
• 空間複雜度：O(n)（對於結果陣列）。

範例輸出：

• 對於價格 = [8, 4, 6, 2, 3]，輸出為 [4, 2, 4, 2, 3]。
• 對於價格 = [1, 2, 3, 4, 5]，輸出為 [1, 2, 3, 4, 5]。
• 對於價格 = [10, 1, 1, 6]，輸出為 [9, 0, 1, 6]。

即使它不是最佳化的解決方案，這種方法也能在問題的限制範圍內發揮作用 (1

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是商店特別折扣的最終價格的詳細內容。更多資訊請關注PHP中文網其他相關文章！