TalkGo算法之美第四期

算法之美
21

周三： 875. 爱吃香蕉的珂珂 



func checkFunc(piles []int, speed, H int) bool {
	needDays := 0
	for _, value := range piles {
		needDays+=value/speed // 每天吃speed个
		if value%speed>0{needDays++} // 不够整除算一天
	}
	
	return needDays<=H
}



func minEatingSpeed(piles []int, H int) int {
	best := -1
	left, right := 1, int(10e9)
	for left<= right {
		mid := (right+left)>>1
		if checkFunc(piles, mid, H) { // 可以吃完
			best, right = mid, mid-1
		} else {
			left = mid+1
		}
	}
	return best
}
22

// 经典二分算法

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func minEatingSpeed(piles []int, H int) int {
    n := len(piles)
    l, r := 1, -1
    for i := 0; i < n; i++ {
        r = maxInt(r, piles[i])
    }

    var calc = func(x int) int {
        ret := 0
        for i := 0; i < n; i++ {
            ret += (piles[i]+x-1)/x
            //ret += piles[i]/x
            //if piles[i]%x > 0 {
            //    ret++
            //}
        }
        return ret
    }

    for l < r {
        mid := l + (r-l)/2
        if calc(mid) > H {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}
23

875

/*
 * @Description: 875
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-10 15:00:51
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-10 15:42:46
 * @FilePath: /875minEatingSpeed/875.go
 */

package leetcode

/*
 二分查找时间
*/
func minEatingSpeed(piles []int, H int) int {

	left := 0
	right := 1000000000
	best := 0
	for left <= right {
		// {"4", args{[]int{2, 2}, 2}, 2}, //导致最后 left：0， right：1， mid得到0
		mid := (right-left)/2 + left
		if eatup(piles, H, mid) {
			best, right = mid, mid-1
		} else {
			left = mid + 1
		}
	}

	return best
}

func eatup(piles []int, H int, speed int) bool {
	if speed == 0 {
		return false
	}

	h := 0
	for pID := range piles {
		if h >= H { //已经过去了h个小时 还没有吃完
			return false
		}
		h += (piles[pID] / speed)
		if piles[pID]%speed > 0 {
			h++
		}
	}

	return !(h > H) //h 到这里表示吃完耗费的小时，如果h==H，也算是满足条件的，这里要注意

}
24

打卡

[162] 寻找峰值

class Solution {
   public:
    int findPeakElement(vector<int>& nums) {
        if (nums.size() == 0) {
            return -1;
        }
        int left = 0, right = nums.size() - 1;
        // 因为最后结果是左边界，这里使用 < 而不是 <=
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 中间相邻两个数字比较，较大的数越接近峰值
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 结果是左边界
        return left;
    }
};

[875] 爱吃香蕉的珂珂

class Solution {
   private:
    bool valid(vector<int>& piles, int H, int K) {
        int hour = 0;
        for (auto& p : piles) {
            // 注意这里计算公式
            hour += (p - 1) / K + 1;
            if (hour > H) {
                return false;
            }
        }
        return true;
    }

   public:
    int minEatingSpeed(vector<int>& piles, int H) {
        if (piles.size() == 0) {
            return 0;
        }
        // 速度的区间是 [1, maxSpeed] ，好歹最少吃一根
        int left = 1, right = 0;
        // 获取一小时最大速度
        for (auto& p : piles) {
            right = max(right, p);
        }
        // 循环，因为最后 left 要作为结果返回，这里使用 < 运算符
        while (left < right) {
            // printf("%d,%d\n", left, right);
            int mid = left + (right - left) / 2;
            if (!valid(piles, H, mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};
25 
func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func shipWithinDays(weights []int, D int) int {
    n := len(weights)
    maxW, sumW := 0, 0
    for i := 0; i < n; i++ {
        maxW = maxInt(maxW, weights[i])
        sumW += weights[i]
    }

    var calc = func(cap int) int {
        ret, ccap := 0, 0
        for i := 0; i < n; i++ {
            if ccap < weights[i] {
                ccap = cap
                ret++
            }
            ccap -= weights[i]
        }
        return ret
    }

    l, r, ret := maxW, sumW, -1 
    for l <= r {
        mid := l + (r-l)/2
        if calc(mid) <= D {
            ret, r = mid, mid - 1
        } else {
            l = mid + 1
        }
    }
    return ret
}
1 个赞
26 

/*
1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500
货物必须按照给定的顺序装运, 给定一个装载量后，顺序一直往里装，装满就换一天运。
*/
func checkFunc(weights []int, D int, overLoad int) bool {
	for curLoad, i:=0, 0; i<len(weights);i++ {
        if weights[i]>overLoad{return false}
		curLoad+=weights[i]
		if curLoad>overLoad{
			curLoad=weights[i]
			D--
		}
		if D<=0 { // 时间用完了
			return false
		}
	} 
	
	return true
}


func shipWithinDays(weights []int, D int) int {
	best := 500*50000
	left, right := 1, best
	for left<= right {
		mid := (right+left)>>1
		if checkFunc(weights, D, mid) { // 可行解，贪心查看有没有更好解, 区间往小移
			best, right = mid, mid-1
		} else {
			left = mid+1
		}
	}
	return best
}
27

// 2021.02.22

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func findBestValue(arr []int, target int) int {
    n := len(arr)
    maxV := arr[0]
    for i := 0; i < n; i++ {
        maxV = max(maxV, arr[i])
    }

    var calc = func(x int) int {
        sum := 0
        for i := 0; i < n; i++ {
            sum += min(arr[i], x)
        }
        return sum
    }

    // >=
    l, r, r1 := 0, maxV, -1
    for l <= r {
        mid := l + (r-l)/2
        if calc(mid) >= target {
            r, r1 = mid - 1, mid
        } else {
            l = mid + 1
        }
    }

    // <= 
    l, r, r2 := 0, maxV, -1 
    for l <= r {
        mid := l + (r-l)/2
        if calc(mid) <= target {
            l, r2 = mid + 1, mid
        } else {
            r = mid - 1
        }
    }

    if r1 == -1 {
        return r2
    }
    if calc(r1)-target >= target-calc(r2) {
        return r2
    }
    return r1    
}
28

双重二分（一年前写的，有点丑）

func check(arr []int , target, mid int) int{
	sum := 0
	for _, num := range arr {
		if num > mid {
			num = mid
		}
		sum +=num
	}
	return sum - target
}
func findBestValue(arr []int, target int) int {
	sort.Ints(arr)
	l := 0
	h := arr[len(arr)-1]+1
	mid := (l+h)/2
	for l != mid && h != mid  {
		if check(arr, target,mid) >0 {
			h = mid
		}else {
			l = mid
		}
        mid = (l+h)/2
	}
    a := check(arr , target, l)
    b:=check(arr , target, h)
    if abs(a)<=abs(b){
        return l
    }
	return h
}
func abs(a int)int{
    if a<=0{
        return -a
    }
    return a
}
29

704. 二分查找

难度简单196收藏分享切换为英文接收动态反馈

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

go

/*
 * @Description:704
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-23 15:20:25
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-23 15:33:00
 * @FilePath: \704search\704.go
 */
package leetcode

import "sort"

func search1(nums []int, target int) int {

	res := sort.SearchInts(nums, target)
	if res == len(nums) {
		return -1
	}

	if nums[res] != target {
		return -1
	}

	return res

}

func search(nums []int, target int) int {

	left, right := 0, len(nums)-1
	for left <= right {
		mid := (right-left)/2 + left
		if nums[mid] == target {
			return mid
		}

		if nums[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}

	}
	return -1

}

rust

/*
 * @Description:
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-23 15:34:05
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-23 15:50:07
 * @FilePath: \704search\search\src\lib.rs
 */
pub struct Solution;

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left: usize = 0;
        let mut right: usize = nums.len() - 1;

        while left <= right {
            let mid = (right - left) / 2 + left;
            if nums[mid] == target {
                return mid as i32;
            }

            if nums[mid] > target {
                if mid == 0{
                    return -1
                }
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }

    pub fn search1(nums: Vec<i32>, target: i32) -> i32 {
        let res = nums.binary_search(&target);
        match res{
            Ok(id)=> id as i32,
            Err(_)=> -1,
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::Solution;

    #[test]
    fn it_works() {
        assert_eq!(Solution::search(vec![-1,0,3,5,9,12], 9),4);
        assert_eq!(Solution::search(vec![-1,0,3,5,9,12], 2),-1);
        assert_eq!(Solution::search(vec![-1,0,3,5,9,12], -2),-1);
        assert_eq!(Solution::search(vec![-1,0,3,5,9,12], 30),-1);

        assert_eq!(Solution::search1(vec![-1,0,3,5,9,12], 9),4);
        assert_eq!(Solution::search1(vec![-1,0,3,5,9,12], 2),-1);
        assert_eq!(Solution::search1(vec![-1,0,3,5,9,12], -2),-1);
        assert_eq!(Solution::search1(vec![-1,0,3,5,9,12], 30),-1);
    }
}
30

34. 在排序数组中查找元素的第一个和最后一个位置

难度中等860收藏分享切换为英文接收动态反馈

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

  • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

go

func searchRange(nums []int, target int) []int {

	left := sort.SearchInts(nums, target)
	if left == len(nums) || nums[left] != target {
		return []int{-1, -1}
	}

	right := sort.SearchInts(nums, target+1)
	return []int{left, right - 1}

}

rust

31

74. 搜索二维矩阵

难度中等323收藏分享切换为英文接收动态反馈

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

go


// 二维数组虚拟为一维数组
func searchMatrix(matrix [][]int, target int) bool {

	row := len(matrix)
	if row == 0 {
		return false
	}

	col := len(matrix[0])
	if col == 0 {
		return false
	}

	beg := 0
	end := row*col - 1
	for beg <= end {

		mid := (end-beg)/2 + beg

		if matrix[mid/col][mid%col] == target {
			return true
		}
		if matrix[mid/col][mid%col] > target {
			end = mid - 1
		} else {
			beg = mid + 1
		}

	}
	return false

}

Rust

impl Solution {
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        let row = matrix.len();
        if row == 0 {
            return false;
        }

        let col = matrix[0].len();
        if col == 0 {
            return false;
        }

        let mut beg = 0;
        let mut end = row * col - 1;
        while beg <= end {
            let mid = (end - beg) / 2 + beg;

            if matrix[mid / col][mid % col] == target {
                return true;
            }
            if matrix[mid / col][mid % col] > target {
                if mid ==0 {
                    return false
                }
                end = mid - 1
            } else {
                beg = mid + 1
            }
        }
        return false;
    }
}

240. 搜索二维矩阵 II

难度中等540收藏分享切换为英文接收动态反馈

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

go


//从右上角开始查询，target更大，往下走，target更小，往左走
func searchMatrix(matrix [][]int, target int) bool {

	rows := len(matrix)
	if rows == 0 {
		return false
	}

	cols := len(matrix[0])
	if cols == 0 {
		return false
	}

	x := 0
	y := cols - 1
	for y >= 0 && x < rows {

		if matrix[x][y] == target {
			return true
		}

		if matrix[x][y] > target {
			y-- //左移动
		} else {
			x++ //下走
		}
	}

	return false

}

Rust

/*
 * @Description:
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-23 16:56:39
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-23 17:10:04
 * @FilePath: \240\search_matrix\src\lib.rs
 */
pub struct Solution;

impl Solution {
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        let rows = matrix.len();
        if rows == 0 {
            return false;
        }

        let cols = matrix[0].len();
        if cols == 0 {
            return false;
        }

        let mut x = 0;
        let mut y = cols - 1;
        while x < rows {
            if matrix[x][y] == target {
                return true;
            }
            //比目标要大 ，向左移动
            if matrix[x][y] > target {
                if y ==0 {
                    return false
                }
                y -= 1;
            } else {
                //比目标值小，向下移动
                x += 1;
            }
        }
        false
    }
}

#[cfg(test)]
mod tests {
    use crate::Solution;
    #[test]
    fn it_works() {
        assert_eq!(Solution::search_matrix(vec![vec![1,4,7,11,15],vec![2,5,8,12,19],vec![3,6,9,16,22],vec![10,13,14,17,24],vec![18,21,23,26,30]],5), true);
        assert_eq!(Solution::search_matrix(vec![vec![1,4,7,11,15],vec![2,5,8,12,19],vec![3,6,9,16,22],vec![10,13,14,17,24],vec![18,21,23,26,30]],-5), false);
    }
}
32

点赞 :100:

33

1300. 转变数组后最接近目标值的数组和

难度中等126收藏分享切换为英文接收动态反馈

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。

请注意，答案不一定是 arr 中的数字。

Go

/*
 * @Description:1300
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-23 17:12:38
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-24 10:25:50
 * @FilePath: \1300findBestValue\1300.go
 */
package leetcode

import "sort"

/*
 分别找小于 target 或 大于targe的组合
 1. arr排序
 2. 求前缀和
 3. 二分查找
*/

func findBestValue1(arr []int, target int) int {

	if len(arr) == 0 {
		return 0
	}

	sort.Ints(arr)
	preSum := make([]int, len(arr))
	for i := range arr {
		preSum[i] = arr[i]
		if i > 0 {
			preSum[i] += preSum[i-1]
		}
	}

	res, diff := 0, target
	for i := 0; i <= arr[len(arr)-1]; i++ {
		id := sort.SearchInts(arr, i+1) //查询比i大的
		sum := (len(arr) - id) * i      //arr[id..]都变为 i
		if id > 0 {
			sum += preSum[id-1]
		}

		if sum == target {
			return i
		}

		if abs(sum-target) < diff {
			res = i
			diff = abs(sum - target)
		}

	}

	return res

}

func abs(x int) int {
	if x < 0 {
		return -x
	}

	return x
}

/*
 分别找小于 target 或 大于targe的组合
 1. arr排序
 2. 求前缀和
 3. 双重二分查找  12ms 5.5MB
*/
func findBestValue(arr []int, target int) int {

	if len(arr) == 0 {
		return 0
	}
	sort.Ints(arr)
	preSum := make([]int, len(arr))
	for i := range arr {
		preSum[i] = arr[i]
		if i > 0 {
			preSum[i] += preSum[i-1]
		}
	}

	//查询大于等于 target 的最小value
	//这里初始值比较重要，left要从0开始，right的最大值就是arr的最大值，更大是没用的
	left, right := 0, arr[len(arr)-1]
	best, sum := 0, 0
	for left <= right {
		mid := (right-left)/2 + left
		sum = computeSum(arr, preSum, mid)
		if sum == target {
			return mid
		}

		if sum > target {
			best, right = mid, mid-1
		} else {
			best, left = mid, mid+1
		}
	}

	best2 := 0
	if sum > target {
		best2 = best - 1
	} else {
		best2 = best + 1
	}

	sum2 := computeSum(arr, preSum, best2)
	if abs(sum-target) < abs(sum2-target) {
		return best
	}

	if abs(sum-target) > abs(sum2-target) {
		return best2
	}

	if best < best2 {
		return best
	}

	return best2
}

func computeSum(arr, preSum []int, mid int) int {
	id := sort.SearchInts(arr, mid+1) //查询大于mid的第一个位置
	sum := (len(arr) - id) * mid      // 大于mid的都变为mid，也就是 arr[id..]都变为 mid
	if id > 0 {
		sum += preSum[id-1]
	}

	return sum
}

1011. 在 D 天内送达包裹的能力

难度中等166收藏分享切换为英文接收动态反馈

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

go

/*
 * @Description: 1011
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-24 10:24:31
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-24 10:53:33
 * @FilePath: \1011shipWithinDays\1011.go
 */
package leetcode

func shipWithinDays(weights []int, D int) int {

	beg := 1 //这个最小值必须是 weights中的最大值，不然这个货物有可能永远都无法上运输带
	end := 0
	best := 0
	for _, v := range weights {
		end += v
		if v > beg {
			beg = v
		}
	}

	for beg <= end {
		mid := (end-beg)/2 + beg
		if match(weights, D, mid) {
			best, end = mid, mid-1
		} else {
			beg = mid + 1
		}
	}

	return best

}

// mid 每日运输多少个
func match(weights []int, D, mid int) bool {

	days := 1
	curWight := 0
	for _, v := range weights {
		if curWight+v > mid { //当天装不下了,放到下一天装
			days++
			curWight = v
			if days > D {
				return false
			}
		} else {
			curWight += v
		}
	}

	return true
}

rust

/*
 * @Description:
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-24 11:00:14
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-24 11:13:08
 * @FilePath: \1011shipWithinDays\ship_within_days\src\lib.rs
 */
pub struct Solution;

impl Solution {
    /*
    二分法，转为是否存在一个threshold，连续子数组的和 不大于 threadhold 的情况下，分为 m 个
    12ms 2.5MB  //跟410题型一样
    */
    pub fn ship_within_days(nums: Vec<i32>, m: i32) -> i32 {
        if nums.len()==0{
            return 0
        }
        let mut beg = nums.iter().max().unwrap().clone() ;
        let mut end: i32 = nums.iter().sum();

        let mut best = 0;
        while beg<=end{
            let mid = (end - beg)/2+beg;
            if Self::exist(&nums, m, mid){
                best = mid;
                end = mid-1;
            }else{
                beg = mid+1;
            }
        }

        return best

    }

    //判断按照 threshold 是否可以分为 最多m 份
    pub fn exist(nums: &Vec<i32>, m: i32, threshold: i32) -> bool {
        let mut cur_day = 1; //当前第几天
        let mut cur_weight = 0;

        for v in nums {
            if cur_weight + v > threshold {
                cur_day += 1;
                cur_weight = *v;
                if cur_day > m {
                    return false;
                }
            }else{
                cur_weight += v;
            }
        }

        true
    }
}

#[cfg(test)]
mod tests {
    use crate::Solution;
    #[test]
    fn it_works() {
        assert_eq!(
            Solution::ship_within_days(vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5),
            15
        );
        assert_eq!(Solution::ship_within_days(vec![3, 2, 2, 4, 1, 4], 3), 6);
        assert_eq!(Solution::ship_within_days(vec![1, 2, 3, 1, 1], 4), 3);
    }
}

162. 寻找峰值

难度中等378收藏分享切换为英文接收动态反馈

峰值元素是指其值大于左右相邻值的元素。

给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

go

/*
 * @Description:
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-24 11:30:48
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-24 11:55:33
 * @FilePath: \162findPeakElement\162.go
 */
package leetcode

//https://talkgo.org/t/topic/1667/18 三分法
func findPeakElement(nums []int) int {
	if len(nums) == 1 {
		return 0
	}

	beg := 0
	end := len(nums)

	for beg < end-1 {

		lmid := (end-beg)/2 + beg
		rmid := (end-lmid)/2 + lmid

		if nums[lmid] >= nums[rmid] {
			end = rmid
		} else {
			beg = lmid
		}
	}
	if nums[beg] > nums[end] {
		return beg
	}

	return end

}
34 
// 1. 二分 + 判定
func maxInt(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func minimumEffortPath(heights [][]int) int {
	n, m := len(heights), len(heights[0])
	minV, maxV := heights[0][0], heights[0][0]
	vis := make([][]bool, n)
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			minV = minInt(minV, heights[i][j])
			maxV = maxInt(maxV, heights[i][j])
		}
		vis[i] = make([]bool, m)
	}

	dx := []int{-1, 1, 0, 0}
	dy := []int{0, 0, -1, 1}

	var clear = func() {
		for i := 0; i < n; i++ {
			for j := 0; j < m; j++ {
				vis[i][j] = false
			}
		}
	}

	var dfs func(x, y, limit int) bool
	dfs = func(x, y, limit int) bool {
		if x == n-1 && y == m-1 {
			return true
		}
		vis[x][y] = true
		for i := 0; i < 4; i++ {
			xx, yy := x+dx[i], y+dy[i]
			if xx >= 0 && xx < n && yy >= 0 && yy < m && absInt(heights[x][y]-heights[xx][yy]) <= limit && !vis[xx][yy] {
				if dfs(xx, yy, limit) {
					return true
				}
			}
		}
		return false
	}

	l, r, ret := 0, maxV-minV, -1
	for l <= r {
		mid := l + (r-l)/2
		clear()
		if dfs(0, 0, mid) {
			ret, r = mid, mid-1
		} else {
			l = mid + 1
		}
	}
	return ret
}

// 2. 并查集
func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func findSet(x int, parent []int) int {
	if parent[x] < 0 {
		return x
	}
	parent[x] = findSet(parent[x], parent)
	return parent[x]
}

func unionSet(x, y int, parent []int) {
	r1, r2 := findSet(x, parent), findSet(y, parent)
	if r1 == r2 {
		return
	}
	if parent[r1] < parent[r2] {
		parent[r1] += parent[r2]
		parent[r2] = r1
	} else {
		parent[r2] += parent[r1]
		parent[r1] = r2
	}
}

type Edge struct {
	u, v, w int
}

func minimumEffortPathTwo(heights [][]int) int {
	n, m := len(heights), len(heights[0])
	edges := make([]Edge, 0, n*m)
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if i+1 < n {
				edges = append(edges, Edge{i*m + j, (i+1)*m + j, absInt(heights[i][j] - heights[i+1][j])})
			}
			if j+1 < m {
				edges = append(edges, Edge{i*m + j, i*m + j + 1, absInt(heights[i][j] - heights[i][j+1])})
			}
		}
	}
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].w < edges[j].w
	})

	parent := make([]int, n*m)
	for i := 0; i < n*m; i++ {
		parent[i] = -1
	}
	for i := 0; i < len(edges); i++ {
		unionSet(edges[i].u, edges[i].v, parent)
		if findSet(0, parent) == findSet(n*m-1, parent) {
			return edges[i].w
		}
	}
	return 0
}

// 3. 最短路径
func maxInt(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func minimumEffortPath(heights [][]int) int {
	n, m := len(heights), len(heights[0])
	dis := make([]int, n*m)
	for i := 1; i < n*m; i++ {
		dis[i] = 0x3f3f3f3f
	}
	dx, dy := []int{-1, 1, 0, 0}, []int{0, 0, -1, 1}
	que := make([]int, 0, 2*n*m)
	inq := make([]bool, n*m)
	que = append(que, 0)
	inq[0] = true
	for len(que) > 0 {
		u := que[0]
		que = que[1:]
		inq[u] = false
		x, y := u/m, u%m
		for i := 0; i < 4; i++ {
			xx, yy := x+dx[i], y+dy[i]
			if xx >= 0 && xx < n && yy >= 0 && yy < m {
				v := xx*m + yy
				w := maxInt(dis[u], absInt(heights[x][y]-heights[xx][yy]))
				if dis[v] > w {
					dis[v] = w
					if !inq[v] {
						inq[v] = true
						que = append(que, v)
					}
				}
			}
		}
	}
	return dis[n*m-1]
}