Steven's Blog

Appearance

On this page

每天一道Rust-LeetCode(2019-11-18) ​

坚持每天一道题,刷题学习Rust.

题目描述 ​

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。 pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。 示例:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/min-stack 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 ​

一开始选择用BTreeSet,但是没有考虑到重复的问题, 如果元素是有重复的,那么就必须使用BTreeMap进行计数才行

解题过程 ​

rust
use std::cmp::min;
use std::collections::BTreeMap;
use std::ops::Bound::Included;
struct Solution {}

impl Solution {
    pub fn contains_nearby_almost_duplicate(nums: Vec<i32>, k: i32, t: i32) -> bool {
        let mut s = BTreeMap::new();
        if t < 0 || k <= 0 || nums.len() <= 0 {
            return false;
        }
        let k = k as usize;
        s.insert(nums[0] as i64, 1);
        for i in 1..nums.len() {
            let n = nums[i] as i64;
            let min = n - t as i64;
            let max = n + t as i64;
            let r = s.range((Included(&min), Included(&max)));
            if r.count() > 0 {
                return true;
            }
            *s.entry(n).or_insert(0) += 1;
            if i >= k {
                //移除第i-k个,保证map里面不会超过k个元素
                let oldest = s.get_mut(&(nums[i - k] as i64)).unwrap();
                if *oldest == 1 {
                    //考虑到有多个的这种情况,比如1出现了多次
                    s.remove(&(nums[i - k] as i64));
                } else {
                    *oldest -= 1;
                }
            }
        }
        false
    }
    pub fn contains_nearby_almost_duplicate2(nums: Vec<i32>, k: i32, t: i32) -> bool {
        if t < 0 || nums.is_empty() || k <= 0 {
            return false;
        }
        let mut min = i32::max_value();
        let mut map: HashMap<i64, i32> = HashMap::new();

        for i in &nums {
            if *i < min {
                min = *i;
            }
        }

        let diff: i64 = t as i64 + 1;

        for iter in 0..nums.len() {
            let i = nums[iter];
            let index: i64 = ((i as i64) - (min as i64)) / diff;
            if let Some(left) = map.get(&(index - 1)) {
                if (i as i64 - (*left as i64)).abs() <= (t as i64) {
                    return true;
                }
            }

            if let Some(right) = map.get(&(index + 1)) {
                if (i as i64 - (*right as i64)).abs() <= (t as i64) {
                    return true;
                }
            }

            if map.get(&index).is_some() {
                return true;
            }

            map.insert(index, i);

            if iter as i32 >= k {
                map.remove(&(((nums[(iter as i32 - k) as usize] as i64) - (min as i64)) / diff));
            }
        }

        false
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    use crate::share::*;

    #[test]
    fn test() {
        assert_eq!(
            Solution::contains_nearby_almost_duplicate(vec![1, 2, 3, 1], 3, 0),
            true
        );
        assert_eq!(
            Solution::contains_nearby_almost_duplicate(vec![1, 0, 1, 1], 1, 2),
            true
        );
        assert_eq!(
            Solution::contains_nearby_almost_duplicate(vec![1, 5, 9, 1, 5, 9], 2, 3),
            false
        );
        assert_eq!(
            Solution::contains_nearby_almost_duplicate(vec![0, 2147483647], 1, 2147483647),
            true
        );
    }
}

一点感悟 ​

因为要求是栈,所以必须存在一个Vector,

还要求常数取得最小,所以必须是排序的,考虑用堆来排序,但是标准库中的堆是不支持任意删除数据的 可以选择BTreeSet,但是因为有数据重复,所以只能是BTreeMap.

当然也可以使用一个有序数组,但是这样插入删除的代价讲师O(N),比二叉树要差不少.

其他 ​

欢迎关注我的github,本项目文章所有代码都可以找到.