ショップでの特別割引を含む最終価格

1475。ショップでの特別割引を含む最終価格

難易度: 簡単

トピック: 配列、スタック、単調スタック

整数の配列pricesが与えられます。price[i]はショップ内のi^番目の商品の価格です。

店内の商品には特別割引があります。 i ^番目 のアイテムを購入すると、prices[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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がショップでの特別割引を含む最終価格の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。