[TOC]

Leetcode刷題

300. 最長遞增子序列【中等】

// ============= 解法一：基本動(dòng)態(tài)規(guī)劃 =============
func lengthOfLIS(nums []int) int {
   if len(nums) <= 1 {
      return len(nums)
   }
   dp := make([]int, len(nums))
   for i := 0; i < len(nums); i++ {
      dp[i] = 1
   }

   res := 1
   for i := 1; i < len(nums); i++ {
      for j := 0; j < i; j++ {
         if nums[i] > nums[j] {
            dp[i] = max(dp[i], dp[j]+1) // 狀態(tài)轉(zhuǎn)移方程，如果num[i]>num[j],說明num[j]
            res = max(res, dp[i])
         }
      }
   }

   return res
}

參考網(wǎng)址：
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/xun-xu-jian-jin-dan-diao-zhan-er-fen-cha-d3hf/

//// ======== 解法二： 單調(diào)棧 + 二分查找 完美契合  =================
func lengthOfLIS(nums []int) int {
   if len(nums) <= 1 {
      return len(nums)
   }
   stack := []int{nums[0]} // 第一個(gè)直接入棧，維護(hù)一個(gè)單調(diào)遞減棧

   for i := 1; i < len(nums); i++ {
      if nums[i] > stack[len(stack)-1] { // 當(dāng)前元素>棧頂元素，直接入棧，棧的單調(diào)遞減特性沒變。
         stack = append(stack, nums[i])
      } else if nums[i] < stack[len(stack)-1] {
         stack = binarySearch_replace(stack, nums[i])
      }
   }
   fmt.Println(stack)
   return len(stack)
}

 
func binarySearch_replace(array []int, target int) []int {
   left, right := 0, len(array)-1
   for left <= right {
      mid := (left + right) / 2
      if array[mid] == target {
         right = mid - 1
      } else if array[mid] > target {
         right = mid - 1
      } else if array[mid] < target {
         left = mid + 1
      }
   }
   array[left] = target
   return array
}