square timeμΌλ‘ μ§λ μ΅μ νλ§ μ νλ©΄ ν΅κ³Όκ° λκΈ΄ ν©λλ€.
λ€λ§ O(N log N), μ¬μ§μ΄λ μ ν μκ°κΉμ§ λ Έλ €λ³Ό μ μλ λ¬Έμ μ λλ€. λ λ€ μ λ§ λ μ°½μ μ΄μμ΅λλ€. κ·Έ μ€μμ λ λΉ λ₯Έ κ²μ μ§μ€νλ κ²μ΄ μ’μΌλ, μ ν μκ° νμ΄λ₯Ό μμΈν λ΄ μλ€.
- κΈ°λ° μμ΄λμ΄λ μΈμμ μ λλ€.
- μ¬μ©ν μκ³ λ¦¬μ¦λ κ½€λ μ λͺ ν, μμ£Ό λ±μ₯νλ ν ν¬λμ λλ€. (λ€λ§ κ²½νμ μΌλ‘, μ΄ ν ν¬λμ΄ νμ μμ μμ£Ό λ±μ₯νμ§λ μμ κ² κ°μ΅λλ€. μ€λ‘μ§ λ¬Έμ νμ΄ μ©λμΌ κ²λλ€.)
μ λͺ¨λ₯΄κ² λλΌλ μ€ν¬ λΉν κ°μΉκ° μΆ©λΆν μμ΅λλ€.
μ€λͺ μ μ‘°κΈ μμΈν μ μ΄λλλ°, λμμ΄ λμ ¨μΌλ©΄ μ’κ² μ΅λλ€.
ν΅μ¬ μμ΄λμ΄λΆν° λ΄ μλ€.
132 λ‘ μ κ·Όνλ 건 κ½€ κΉλ€λ‘μ΅λλ€. λͺ¨λ μ ν¨ν ꡬκ°μ μ μ₯νκ³ , κ·Έ ꡬκ°λ€ μ€ μ΄λκ°μ μνλμ§ μ²΄ν¬ν΄λ΄μΌ νκΈ° λλ¬Έμ λλ€. λ¬Όλ‘ μ΄μ§ νμμ μ μ¨μ O(N log N)μΌλ‘ μ€μ¬λ³Ό μλλ ν μ μκ² μ§λ§, μ½λκ° μλ 볡μ‘ν΄μ§ κ² κ°λ€μ.
κ·Έλμ, λ°°μ΄μ λ€μ§μ΄λ΄ μλ€. 231 λ¬Έμ κ° λ©λλ€. κ·Έλ¬λ©΄ μ κ·Όλ²μ΄ μ΄λ κ² λ°λλλ€.
- μ§κΈκΉμ§ 체ν¬ν μ«μλ€μ 2 ν보λΌκ³ ν©μλ€. κ·Έ μλ³΄λ€ ν° μ(3)κ° λ€μ΄μλ€λ©΄ μ ν¨ν 2κ° λ©λλ€.
- μ μ«μκ° λ€μ΄μμ λ, κ·Έ μ«μκ° μ ν¨ν 2μ€ νλλ³΄λ€ μμΌλ©΄ μ ν¨ν 1μ΄ λ©λλ€. λ°λΌμ 231μ μ°Ύμ κ²μΌλ‘ μκ³ λ¦¬μ¦μ΄ μ’ λ£λ©λλ€.
- μ΄λ€ μμ μμ μ ν¨ν 2κ° μ¬λ¬κ° μμ λ, κ·Έ μ€μμ κ°μ₯ ν° κ²λ§ 보면 λ©λλ€. λλ¨Έμ§λ λ²λ €λ λ©λλ€.
ꡬκ°μ κΈ°λ‘ν νμλ μμ΄μ‘κ³ , λͺ¨λ μ ν¨ν κ²λ€μ κΈ°λ‘ν νμλ μμ΄μ‘μ΅λλ€. λ¬Έμ κ° λ κ°κ²°ν΄μ‘μ£ .
μ΄μ μ΄ μ κ·Όλ²μ μ ν μκ°μΌλ‘ ꡬνν ν ν¬λμ μκ°νκ² μ΅λλ€. λ°λ‘ λͺ¨λ Έν λ μ€νμ λλ€. μ€νμ κ·Έλ₯ νλ²νκ² λ΄μ₯ λΌμ΄λΈλ¬λ¦¬μμ κ°λ€ μλλ€. λμ μ ν¬κ° μ½λλ₯Ό μ μ§μ μ€νμ λ κ°λ€μ΄ νμ λͺ¨λ Έν λνλλ‘ μ μ§νλ ν ν¬λμ λλ€. κ·Έλμ ν ν¬λμ΄λΌλ ννμ μΌμ΅λλ€.
μ΄λ λͺ¨λ Έν λμ, λͺ¨λ μμκ° νμ μ¦κ°(a[i-1] β€ a[i])νκ±°λ νμ κ°μ(a[i-1] β₯ a[i])νκ±°λλ₯Ό μλ―Έν©λλ€. λΉμ°ν λ μ€ νλλ§ κ°λ₯ν©λλ€.
λμ²΄λ‘ ν¨ν΄μ μ΄λ μ΅λλ€. μ¦κ°νλ μ€ν κΈ°μ€μΌλ‘ λ΄ μλ€. μμ΄μ μννλ©΄μ μ€νμ κ°μ λ£μ΅λλ€. λ§μ½ νμ¬ μμκ° μ€ν νλ³΄λ€ ν¬λ€λ©΄, κ·Έλ₯ νΈμνλ©΄ λ©λλ€. λ§μ½ νμ¬ μμκ° μ€ν νλ³΄λ€ μλ€λ©΄, νΈμνλ©΄ λͺ¨λ Έν λμ΄ κΉ¨μ§λλ€. κ·Έλμ νμ¬ μμλ³΄λ€ μμ κ²λ€μ λͺ¨μ‘°λ¦¬ popν΄μ, λͺ¨λ Έν λμ΄ λλλ‘ μλμΌλ‘ λ§λλλ€. κ·Έ λ€μ μ΄ν¬μ νΈμνλ©΄ λ©λλ€.
μ΄ μΉκ΅¬λ μμ£Ό μ¬κΈ°μ μ λλ€. μ¬μ©ν μ μλ μν©μ΄λΌλ©΄, 무쑰건 O(N)μ μκ°λ³΅μ‘λλ₯Ό 보μ₯νκΈ° λλ¬Έμ λλ€. κ·Έλμ λ¬Έμ κ° N^2μ λλ‘ μ λ ₯ λ°°μ΄μ νμν΄μΌ ν κ²μ²λΌ 보μ΄λλ°, λ§μ Nμ΄ μλ§ μ΄μμ΄λΌλ©΄, λͺ¨λ Έν λ μ€ν μμ© λ¬Έμ μΌ κ°λ₯μ±μ ν λ²μ―€ μκ°ν΄λ΄μΌ ν©λλ€.
λ°±μ€μμ κ΄λ ¨ λ¬Έμ λ 골λ4~νλ 3κΉμ§ λΆν¬νκ³ μλ κ±Έ λ΄€μ΅λλ€. λμ΄λ λμ μ€ν λ¬Έμ λ κ±°μ λ€ μ΄κ±°λΌκ³ 보μλ©΄ λ©λλ€. 17298λ² κ³¨λ4 μ€ν°μκ° μ λͺ ν λ¬Έμ μ€ νλμΈλ°, μμν μ‘°κ±΄μ΄ μμ΄μ μ΄ ν ν¬λ μ λ¬Έμ©μΌλ‘ κ°μΆν©λλ€. (ꡬκΈλ§ν΄κ°λ©° μ΄ν΄λ λκΉμ§ ν΄λ³΄μκΈΈ μΆμ²λλ €μ.) νΉν 1725λ² νλ 5 νμ€ν κ·Έλ¨ λ¬Έμ κ° μμ£Ό μ λͺ ν μ νμ λλ€. μ΄κ²λ§ μ μ΅νλ©΄ νλ λ¬Έμ λͺ κ°λ₯Ό λ λ¨Ήν μ μμ΅λλ€.
리νΈμ½λμλ λͺ¨λ Έν λ μ€ν νκ·Έκ° λ°λ‘ μμ΅λλ€.
본격μ μΈ νμ΄μ λλ€. μ°μ μμ ν κ²μ²λΌ λ°°μ΄μ λ€μ§μμ΅λλ€.
βμ ν¨ν 2μ€ μ΅λκ°β λ³μλ₯Ό λ§λ€μ΄λ‘μλ€. μΌλ¨μ κ·Έλ λ€κ³ κ°μ ν΄λκ³ , μμΈν κ²μ νμ νκ² μ΅λλ€. λ°°μ΄μ μννλ©΄μ, μ μμκ° κ·Έ λ³μλ³΄λ€ μλ€λ©΄ μ ν¨ν 1μ΄λ―λ‘ μΌκ³ 리μ¦μ μ¦κ° μ’ λ£μν΅λλ€.
μ΄ λ¬Έμ μμλ λ¨μ‘° κ°μ(monotonic decreasing)λ₯Ό μΈ κ²λλ€. μ μμκ° μ€ν νλ³΄λ€ μλ€λ©΄, κ·Έλ₯ νΈμν©λλ€.
μ μμκ° μ€ν νλ³΄λ€ ν° κ²½μ°λ₯Ό λ΄ μλ€. κ·Έλ¬λ©΄ μ€ν νμ μ ν¨ν 2λ‘, μ μμλ₯Ό 3μΌλ‘ λ³Ό μ μμ΅λλ€. κ·Έλ λ€λ©΄ μ΄νμ μ ν¨ν 2λ³΄λ€ μμ μκ° λ°κ²¬λλ€λ©΄ κ·Έκ²μ΄ μ ν¨ν 1μΌ κ²μ΄κ³ , μκ³ λ¦¬μ¦μ΄ μ’ λ£λκ² μ£ .
μ΄λ° λ°©μμΌλ‘ μ€ν νμ popνκ³ , popν μ«μλ₯Ό βμ ν¨ν 2μ€ μ΅λκ°β λ³μμ κΈ°λ‘ν΄λ‘μλ€. λ³Έλ κΈ°μ‘΄ μ΅λκ°λ³΄λ€ λ ν°μ§λ₯Ό νλ³νκ³ μ max ν¨μ μ¬μ©μ κ³ λ €ν΄μΌ νμ§λ§, μ΄ λ¬Έμ μμλ βμ ν¨ν 2μ€ μ΅λκ°βλ³΄λ€ λ μμ μκ° λ°κ²¬λλ©΄ μ¦κ° μκ³ λ¦¬μ¦μ΄ μ’ λ£λ©λλ€. μ¦, popλ μ«μκ° κΈ°μ‘΄ μ΅λκ°λ³΄λ€ μμ κ²½μ°λ μ μ΄μ μ€νμ λ€μ΄κ°κΈ°λ μ μ λλλ―λ‘ κ³ λ €νμ§ μμλ λ©λλ€. λν μ€νμ λ¨μμλ μ«μλ νμ νμ¬ βμ ν¨ν 2μ€ μ΅λκ°βλ³΄λ€ ν¬λ€κ³ λ³Ό μ μμ΅λλ€.
λͺ¨λ
Έν λ μ€νμ νΉμ§μ, μ μμμ λν΄ popν΄μΌ νλ μ«μκ° μ¬λΏμΌ μ μλ€λ κ²μ
λλ€.
κ·Έλμ while
λ°λ³΅λ¬Έμ νμ©ν©λλ€.
μλ‘μ΄ μ€ν νΌν¬λ λ°©κΈ popν κ²λ³΄λ€ λ ν¬λ€λ μ μ΄ νΉμ§μ
λλ€.
(λ¬Έμ μ νμ λ°λΌ βκ°κ±°λ ν¬κ²β μ μ§νκΈ°λ, λ¨μ‘° μ¦κ° μ€νμ μ°κΈ°λ ν©λλ€.)
λ§μ§λ§μΌλ‘ μ μμ κ·Έ μ체λ 2 ν보μ΄λ―λ‘ μ€νμ λ£μ΅λλ€.
μ΄ λ΄μ©μ κ°λ¬΄λ¦¬ν κ²μ΄ μλ μ½λμ λλ€. μκ°λ³΄λ€ κ°κ²°ν©λλ€.
Given an array of n
integers nums
, a 132 pattern is a subsequence of three integers nums[i]
, nums[j]
and nums[k]
such that i < j < k
and nums[i] < nums[k] < nums[j]
.
Return true
if there is a 132 pattern in nums
, otherwise, return false
.
Example 1:
Input: nums = [1,2,3,4] Output: false Explanation: There is no 132 pattern in the sequence.
Example 2:
Input: nums = [3,1,4,2] Output: true Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
Input: nums = [-1,3,2,0] Output: true Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
Constraints:
n == nums.length
1 <= n <= 2 * 105
-109 <= nums[i] <= 109