976. 三角形的最大周長（java）

題目連結 

976. 三角形的最大周長 - 力扣

https://leetcode-cn.com/problems/largest-perimeter-triangle/

題目描述

給定由一些正數（代表長度）組成的數組 

A

，傳回由其中三個長度組成的、面積不為零的三角形的最大周長。

如果不能形成任何面積不為零的三角形，傳回 

。

示例 

輸入：[2,1,2]
輸出：5      

輸入：[1,2,1]
輸出：0      

輸入：[3,2,3,4]
輸出：10      

輸入：[3,6,2,3]
輸出：8      

解題思路 

依次周遊 + 最大堆（優先隊列）

從題目中我們可以知道，該題要求的是 “ 傳回可以組成三角形的最大周長”。

是以我們可以周遊該數組，把數組中的資料放入最大堆（通過重寫對數器中的方法改變其排列順序）。

先從堆中彈出三個資料cur1，cur2，cur3，然後 當堆不為空時，每次彈出一個資料。

始終讓cur1為最大，cur2為次大，cur3為第三大（即新彈出的資料）。

如果cur1 < cur2  +  cur3，即滿足三角形成立的條件，傳回他們的和即可。 

貪心政策：即保持每次選擇的資料為目前最大。

代碼 

class Solution {
    public int largestPerimeter(int[] nums) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for(int item : nums){
            maxHeap.offer(item);
        }
        int cur1 = maxHeap.poll();
        int cur2 = maxHeap.poll();
        int cur3 = maxHeap.poll();
        if(cur1 < cur2 + cur3){
            return cur1 + cur2 + cur3;
        }
        while(!maxHeap.isEmpty()){
            cur1 = cur2;
            cur2 = cur3;
            cur3 = maxHeap.poll();
            System.out.println(cur3);
            if(cur1 < cur2 + cur3){
                return cur1 + cur2 + cur3;
            }
        }
        return 0;
    }
}
           

補充 

 有關優先隊列的知識可以看看一看相關的部落格，連結在下面哦。

 Java優先隊列（PriorityQueue）_try to do-CSDN部落格

感覺好久沒更新了呀，最近要準備期中考試了，少更一些咯。