akmhmgc · akmhmgc · Oct 11, 2025 · potrue · Oct 11, 2025 · akmhmgc
diff --git a/31/step1.md b/31/step1.md
@@ -0,0 +1,51 @@
+# step1 何も見ずに解く
+複数の例で考えた。
+先頭から隣同士の数字を見ていき、最後に増加した手前のインデックスをiとする
+そのインデックスの値より大きい値で、最も後ろにあるものをjとする
+iとjの値を交換すると、i + 1から末尾までは降順になるので、順序を逆にすればnext permutationになる。
+
+例えば[1, 9, 5, 4, 3, 2]を考える。
+最後に増加した手前のインデックスは0
+その値より大きい値で最も後ろにあるのは5
+それぞれを入れ替えると[2, 9, 5, 4, 3, 1]になる。
+次に、9, 5, 4, 3, 1の部分を逆にすると[2, 1, 3, 4, 5, 9]となり、next permutationが出る。
+時間計算量は配列の長さをNとするとO(N)でNの最大値は100なので時間は問題ない。
+空間計算量はO(1)
+
+
+last_increasing_indexが見つからない時の処理を忘れて最初に間違えた。
+```ruby
+# @param {Integer[]} nums
+# @return {Void} Do not return anything, modify nums in-place instead.
+def next_permutation(nums)
+    return nums if nums.size == 1
+
+    reverse = lambda do |left, right|
+        while left < right
+            nums[left], nums[right] = nums[right], nums[left]
+            left += 1
+            right -= 1
+        end
+    end
+
+    last_increasing_index = -1
+    (nums.size - 1).times do |i|
+        j = i + 1
+        next if nums[i] >= nums[j]
+        last_increasing_index = i
+    end
+    if last_increasing_index == -1
+        reverse.call(0, nums.size - 1)
+        return
+    end
+    last_greater_index = -1
+    (nums.size - 1).downto(0).each do |i|
+        if nums[i] > nums[last_increasing_index]
+            last_greater_index = i
+            break
+        end
+    end
+    nums[last_increasing_index], nums[last_greater_index] = nums[last_greater_index], nums[last_increasing_index]
+    reverse.call(last_increasing_index + 1, nums.size - 1)
+end
+```
diff --git a/31/step2.md b/31/step2.md
@@ -0,0 +1,55 @@
+# step2 他の方の解答を見る
+## step1の解法の改善
+- https://github.com/olsen-blue/Arai60/pull/59
+
+step1の`last_increasing_index`も、`last_greater_index`と同様に右から探せばよかった。
+Rubyにはないが、伝わりやすいのでrfindという名前を参考にした。
+> rfind という名前を使うなら built-in の規則に合わせたくなります。
+
+確かに。RubyだとArrayの捜査系のメソッドで-1を返すことはないのでnilでも良いのかもしれない…と思ったけどモンキーパッチ当ててArrayにメソッドを生やしているわけではないからどっちも良いかもしれん。
+
+- https://github.com/tokuhirat/LeetCode/pull/58
+`rfind_pivot`, `rfind_successor`としていて、コメントで補足する方法。
+
+- https://github.com/ryosuketc/leetcode_arai60/pull/58
+`rfind_not_descending`
+
+1135みたいな並びだと最初の右側の1を探したいのでnot_descendingはいいかも
+
+```ruby
+# @param {Integer[]} nums
+# @return {Void} Do not return anything, modify nums in-place instead.
+def next_permutation(nums)
+    return nums if nums.size == 1
+
+    reverse = lambda do |left, right|
+        while left < right
+            nums[left], nums[right] = nums[right], nums[left]
+            left += 1
+            right -= 1
+        end
+    end
+    rfind_first_not_descending = lambda do
+        (nums.size - 2).downto(0).each do |i|
+            return i if nums[i] < nums[i + 1]
+        end
+        nil
+    end
+    rfind_first_greater_than = lambda do |target|
+         (nums.size - 1).downto(0).each do |i|
+            return i if nums[i] > target
+         end
+         nil
+    end
+
+    pivot_index = rfind_first_not_descending.call
+    if pivot_index.nil?
+        nums.reverse!
+        return
+    end
+    swap_index = rfind_first_greater_than.call(nums[pivot_index])
+    nums[pivot_index], nums[swap_index] = nums[swap_index], nums[pivot_index]
+    reverse.call(pivot_index + 1, nums.size - 1)
+end
+```
+
diff --git a/31/step3.md b/31/step3.md
@@ -0,0 +1,35 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {Integer[]} nums
+# @return {Void} Do not return anything, modify nums in-place instead.
+def next_permutation(nums)
+    reverse = lambda do |left, right|
+        while left < right
+            nums[left], nums[right] = nums[right], nums[left]
+            left += 1
+            right -= 1
+        end
+    end
+    rfind_first_ascending = lambda do
+        (nums.size - 2).downto(0).each do |i|
+            return i if nums[i] < nums[i + 1]
+        end
+        nil
+    end
+    rfind_first_greater_than = lambda do |target|
+        (nums.size - 1).downto(0).each do |i|
+            return i if nums[i] > target
+        end
+        nil
+    end
+    pivot_index = rfind_first_ascending.call
+    if pivot_index.nil?
+        nums.reverse!
+        return
+    end
+    swap_index = rfind_first_greater_than.call(nums[pivot_index])
+    nums[pivot_index], nums[swap_index] = nums[swap_index], nums[pivot_index]
+    reverse.call(pivot_index + 1, nums.size - 1)
+end
+```
diff --git a/31/step4.md b/31/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正