300. 最长递增子序列

  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         // 键值对的含义：最长上升序列中的第key个数是value，或者说，长度为key的上升序列的最大值为value
  4.         // key的取值范围是[1,最长上升序列的长度]，因此，hashMap中键值对的个数就是最长上升序列的长度
  5.         // 初始时，最长上升序列中仅有1个数即nums[0]，或者说，初始时长度为1的上升序列的最大值为nums[0]
  6.         HashMap<Integer, Integer> hashMap = new HashMap<>();
  7.         hashMap.put(1, nums[0]);
  8.         for (int i = 1; i < nums.length; i++) {
  9.             for (int j = hashMap.size(); j >= 1; j--) {
  10.                 if (nums[i] > hashMap.get(j)) { // 若nums[i]比长度为j的上升序列的最大值更大
  11.                     hashMap.put(j + 1, nums[i]); // 则增加或更新长度为(j+1)的上升序列的最大值(换了个更小的nums[i])
  12.                     break;
  13.                 }
  14.             }
  15.             if (nums[i] < hashMap.get(1)) { // 若nums[i]比最长上升序列的最小值更小
  16.                 hashMap.put(1, nums[i]); // 则更新最长上升序列的最小值
  17.             }
  18.         }
  19.         return hashMap.size();
  20.     }
  21. }