From bda98821cdae104dccf91644b5f2ba92a211d94b Mon Sep 17 00:00:00 2001 From: akmhmgc Date: Thu, 25 Sep 2025 17:45:33 +0900 Subject: [PATCH] 121 --- 121/step1.md | 24 ++++++++++++++++++++++++ 121/step2.md | 6 ++++++ 121/step3.md | 20 ++++++++++++++++++++ 121/step4.md | 1 + 4 files changed, 51 insertions(+) create mode 100644 121/step1.md create mode 100644 121/step2.md create mode 100644 121/step3.md create mode 100644 121/step4.md diff --git a/121/step1.md b/121/step1.md new file mode 100644 index 0000000..c144c6d --- /dev/null +++ b/121/step1.md @@ -0,0 +1,24 @@ +# step1 何も見ずに解く + +ある日に売る時に得られる最大の利益は、「ある日での売り値 - ある日以前での最安値」で求めることができる。 +ある日以前の最安値と、最大の利益を変数で更新していけば時間計算量O(N)となり、Nの最大値は10^5なので1秒以内に間に合う。 +空間計算量はO(1) + +```ruby +# @param {Integer[]} prices +# @return {Integer} +def max_profit(prices) + prices_size = prices.size + return 0 if prices_size <= 1 + + min_price = prices.first + max_profit = 0 + (1...(prices_size)).each do |i| + price = prices[i] + max_profit = [max_profit, price - min_price].max + min_price = [min_price, price].min + end + max_profit +end +``` + diff --git a/121/step2.md b/121/step2.md new file mode 100644 index 0000000..7de4a64 --- /dev/null +++ b/121/step2.md @@ -0,0 +1,6 @@ +# step2 他の方の解答を見る + +https://github.com/hayashi-ay/leetcode/pull/52/files#diff-0474f0ee7711182f0e97bb4047531dc4c65356748eafab139512400ac88c5c0bR67-R79 + +後ろから見て売る時の最高値を更新していき、最安値の時に買うパターン。 +個人的には買う->売るという作業の流れを逆にしたくないので好みではない。 diff --git a/121/step3.md b/121/step3.md new file mode 100644 index 0000000..c7de26f --- /dev/null +++ b/121/step3.md @@ -0,0 +1,20 @@ +# step3 3回続けて10分以内に書いてエラーを出さなければOKとする + +step1と同じになった。 +```ruby +# @param {Integer[]} prices +# @return {Integer} +def max_profit(prices) + prices_size = prices.size + return 0 if prices_size <= 1 + + min_price = prices.first + max_profit = 0 + (1...(prices_size)).each do |i| + price = prices[i] + max_profit = [max_profit, price - min_price].max + min_price = [min_price, price].min + end + max_profit +end +``` diff --git a/121/step4.md b/121/step4.md new file mode 100644 index 0000000..5941ee1 --- /dev/null +++ b/121/step4.md @@ -0,0 +1 @@ +## step4 レビューを受けて解答を修正