[TOC]
Leetcode刷题
300. 最长递增子序列【中等】
// ============= 解法一：基本动态规划 =============
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) // 状态转移方程，如果num[i]>num[j],说明num[j]
res = max(res, dp[i])
}
}
}
return res
}
参考网址：
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/xun-xu-jian-jin-dan-diao-zhan-er-fen-cha-d3hf/
//// ======== 解法二： 单调栈 + 二分查找 完美契合 =================
func lengthOfLIS(nums []int) int {
if len(nums) <= 1 {
return len(nums)
}
stack := []int{nums[0]} // 第一个直接入栈，维护一个单调递减栈
for i := 1; i < len(nums); i++ {
if nums[i] > stack[len(stack)-1] { // 当前元素>栈顶元素，直接入栈，栈的单调递减特性没变。
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
}
