CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

    • 栈理论基础
    • 剑指 Offer 06 - 从尾到头打印链表
    • 剑指 Offer 09 - 用两个栈实现队列
    • 有效的括号
    • 删除字符串中的所有相邻重复项
    • 后缀表达式
    • 表达式求值
    • 字符串解码
    • 小行星碰撞
      • 📃 题目描述
      • 🔔 解题思路
      • 💥 复杂度分析
    • 剑指 Offer 30 - 包含 min 函数的栈
    • 剑指 Offer 31 - 栈的压入、弹出序列
    • 单调栈问题

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 栈
小牛肉
2022-04-14
目录

小行星碰撞

# 📃 题目描述

题目链接:

  • 剑指 Offer II 037. 小行星碰撞 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
  • 735. 行星碰撞 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)

# 🔔 解题思路

题目需要明确两点:

1)只有一种情况下会发生碰撞:栈顶行星往右走(> 0), 当前行星往左走(< 0)

2)发生爆炸后,若当前行星仍然存活,那么他会继续向左推进

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        while (index < asteroids.length) {
            // 只有栈顶行星向右,当前行星向左,才会发生碰撞
            if (!stack.isEmpty() && asteroids[index] < 0 && stack.peek() > 0) {
                // 1. 栈顶行星大小 < 当前行星:栈顶行星爆炸,当前行星继续推进
                if (stack.peek() < -asteroids[index]) {
                    stack.pop();
                }
                // 2. 栈顶行星大小 == 当前行星:共同爆炸,进入下一个行星的处理
                else if (stack.peek() == -asteroids[index]) {
                    stack.pop();
                    index ++;
                }
                // 3. 栈顶行星大小 > 当前行星:当前行星爆炸,进入下一个行星的处理
                else {
                    index ++;
                }
            }
            // 4. 不发生碰撞或者栈为空
            else {
                stack.push(asteroids[index]);
                index ++;
            }
        }
        

        return stack.stream().mapToInt(Integer::intValue).toArray();
    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
字符串解码
剑指 Offer 30 - 包含 min 函数的栈

← 字符串解码 剑指 Offer 30 - 包含 min 函数的栈→

最近更新
01
关于编程满天星
02
让我来告诉你 Java 程序员是怎么一步一步从入行到被裁的
06-08
03
Vision Pro,未来已来
06-06
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式