国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

LeetCode[132] Pattern

go4it / 1201人閱讀

摘要:復雜度思路維護一個里面有最大值和最小值。如果當前值小于的最小值,那么就將原來的壓進去棧,然后在用這個新的的值再進行更新。如果沒有適合返回的值,就重新更新當前的。

Leetcode[132] Pattern

Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:
Input: [1, 2, 3, 4]
Output: False
Explanation: There is no 132 pattern in the sequence.

Example 2:
Input: [3, 1, 4, 2]
Output: True
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Stack

復雜度
O(N),O(N)

思路
維護一個pair, 里面有最大值和最小值。如果當前值小于pair的最小值,那么就將原來的pair壓進去棧,然后在用這個新的pair的值再進行更新。如果當前值大于pair的最大值,首先這個值和原來在stack里面的那些pair進行比較,如果這個值比stack里面的值的max要大,就需要pop掉這個pair。如果沒有適合返回的值,就重新更新當前的pair。

代碼

Class Pair {
    int min;
    int max;
    public Pair(int min, int max) {
        this.min = min;
        this.max = max;
    }
}

public boolean find123Pattern(int[] nums) {
    if(nums == null || nums.length < 3) return false;
    Pair cur = new Pair(nums[0], nums[0]);
    Stack stack = new Stack<>();
    for(int i = 1; i < nums.length; i ++) {
        if(nums[i] < cur.min) {
            stack.push(cur);
            cur = new Pair(nums[i], nums[i]);
        }
        else if(nums[i] > cur.max) {
            while(!stack.isEmpty() && stack.peek().max <= nums[i]) {
                stack.pop();
            }
            if(!stack.isEmpty() && stack.peek.max > nums[i]) {
                return true;
            }
            cur.max = nums[i];
        }
        else if(nums[i] > cur.min && nums[i] < cur.max) {
            return true;
        }
    }
    return false;
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/69793.html

相關文章

  • 132pattern

    摘要:記錄即之前,里的最小值,即題目里的即所有不滿足的直接跳過。已知那么找一個比大,又盡可能小的數找滿足就最可能。找到后,比較是否滿足滿足就返回更新棧頂元素,表示表示 Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k an...

    Raaabbit 評論0 收藏0
  • leetcode132. Palindrome Partitioning II

    摘要:題目要求現在有一個字符串,將分割為多個子字符串從而保證每個子字符串都是回數。我們只需要找到所有可以構成回數的并且得出最小值即可。即將字符作為,將字符所在的下標列表作為。再采用上面所說的方法,利用中間結果得出最小分割次數。 題目要求 Given a string s, partition s such that every substring of the partition is a ...

    jeyhan 評論0 收藏0
  • [leetcode]132. Palindrome Partitioning II

    摘要:用表示當前位置最少需要切幾次使每個部分都是回文。表示到這部分是回文。如果是回文,則不需重復該部分的搜索。使用的好處就是可以的時間,也就是判斷頭尾就可以確定回文。不需要依次檢查中間部分。 Given a string s, partition s such that every substring of the partition is a palindrome. Return the...

    Airy 評論0 收藏0
  • 【實踐】玩轉正則表達式+JS正則處理函數

    摘要:前言寫這篇文章不是空穴來風,最近一個禮拜寫了一個簡單的腳本,用來處理上千個文件,以便于在某些特定字符的周圍添加標記,先說一下我這個腳本使用場景主要是來識別中文具體做什么,之后會單獨寫一篇文章,此處只提該腳本作用,同時為不同的文件類型,包括, 前言 寫這篇文章不是空穴來風,最近一個禮拜寫了一個簡單的nodejs腳本,用來處理上千個文件,以便于在某些特定字符的周圍添加標記,先說一下我這個腳...

    DoINsiSt 評論0 收藏0
  • [Leetcode] Permutation Sequence 全排列序列

    摘要:找規律復雜度時間空間思路由于我們只要得到第個全排列,而不是所有全排列,我們不一定要將所有可能都搜索一遍。根據全排列順序的性質,我們可以總結出一個規律假設全排列有個數組成,則第個全排列的第一位是。然后將得到,這個就是下一輪的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

    testHs 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<